Distinct Palindromic Substrings

You are given a number of test cases. In each test case, you are provided with a string.

Your task is to calculate the number of distinct palindromic substrings for each string.

A palindrome is a string that reads the same forwards and backwards. Mathematically, for a substring \( S \), it is palindromic if \( S = S^R \), where \( S^R \) denotes the reverse of \( S \).

Note that even a single character is considered a palindrome. For example, for the string "abaaa", the distinct palindromic substrings are: "a", "b", "aba", "aa", "abaaa" (total = 5).

inputFormat

The first line contains a single integer \( T \) denoting the number of test cases.

Each of the following \( T \) lines contains a non-empty string.

Input Format:

T
s1
s2
...
sT

outputFormat

For each test case, output a single line containing one integer --- the number of distinct palindromic substrings found in the input string.

Output Format:

result1
result2
...
resultT

## sample

3
a
b
c

1
1
1

</p>