Count Palindromic Substrings

You are given T test cases. For each test case, an input string s is provided. Your task is to compute the number of palindromic substrings in each string. A palindromic substring is a contiguous segment of characters that reads the same backward as forward.

For example, for the string aba, the palindromic substrings are: a, b, and aba. Note that even if a palindrome appears multiple times, each occurrence is counted separately.

The relation of indices in a palindrome can be illustrated as follows: if a substring s[i...j] is a palindrome then \[ s[i] = s[j],\; s[i+1] = s[j-1],\; \ldots \]

This problem requires an efficient approach; solutions using center expansion to check palindromes are recommended.

inputFormat

The first line of the input contains an integer T representing the number of test cases. The next T lines each contain a string s for which you need to count the palindromic substrings. Note that a string may be empty.

outputFormat

For each test case, output a single integer on a new line that denotes the number of palindromic substrings in the given string.

## sample

3
abc
aaa
ababa

3
6
9

</p>