Counting Palindromic Substrings

You are given a string and are required to count the number of palindromic substrings in it. A substring is a contiguous sequence of characters in a string. A palindrome is a string that reads the same backward as forward. Formally, for a string \( s \) of length \( n \), a substring \( s[i \dots j] \) (with \( 0 \le i \le j < n \)) is palindromic if:

\[ s[i] = s[j], \quad s[i+1] = s[j-1], \quad \ldots \]

Your task is to compute this count for each test case provided. Use an efficient method such as center expansion to check for palindromes.

inputFormat

The first line of input consists of a single integer \( T \) representing the number of test cases. Each test case consists of a single line containing a non-empty string \( s \). The string \( s \) is composed of lowercase English letters.

outputFormat

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

## sample

3
aba
abc
aaa

4
3
6

</p>