Count Palindromic Substrings

Given a string S, your task is to count the total number of palindromic substrings in S. A palindromic substring is a substring that reads the same backwards as forwards. Note that single characters are considered palindromic substrings. For example, in the string abba, the palindromic substrings are: a, b, b, a, bb, and abba, making a total of 6 palindromic substrings.

The expected time complexity of your solution is $O(n^2)$ where $n$ is the length of the string.

inputFormat

The first line of input contains an integer T representing the number of test cases. Each of the next T lines contains a single string S.

outputFormat

For each test case, output a single line containing the number of palindromic substrings in the given string.

1
abba

6