Distinct Palindromic Substrings

Given a string S, your task is to count the number of distinct substrings of S that are palindromic. A palindrome is a string that reads the same backwards as forwards. For example, in the string "aabaa", the distinct palindromic substrings are: "a", "aa", "aabaa", "aba", and "b".

You are required to process multiple test cases. For each test case, the first line contains an integer T representing the number of test cases. Each of the following T lines contains a string S for which you have to compute the number of distinct palindromic substrings. The answer for each test case should be printed on a new line.

Note: When a formula is used, it should be written in LaTeX. In this problem, if necessary, you can express the length of the string as $n$.

inputFormat

The input is given from standard input (stdin) and has the following format:

T
S1
S2
...
ST

Where T is the number of test cases, and each S_i is a non-empty string.

outputFormat

For each test case, output the number of distinct palindromic substrings in the string S on a separate line to standard output (stdout).

## sample

3
aabaa
banana
abc

5
6
3

</p>