Distinct Palindromic Substrings

You are given a string s and your task is to compute the number of distinct palindromic substrings it contains. A substring is a contiguous sequence of characters within a string. A string is said to be a palindrome if it reads the same forwards and backwards. Mathematically, a string s is a palindrome if $$ s = s^R $$, where $$ s^R $$ represents the reverse of s.

For example, for the string ababa, the distinct palindromic substrings are: a, b, aba, bab and ababa, so the answer is 5.

You need to support multiple test cases. The first line of the input contains an integer T denoting the number of test cases. Each of the following T lines contains a single string. For each test case, output the number of distinct palindromic substrings on a separate line.

inputFormat

The input begins with an integer T (1 ≤ T ≤ 100), which denotes the number of test cases. Each of the following T lines contains a non-empty string s consisting of lowercase English letters. It is guaranteed that the length of s is not very large.

outputFormat

For each test case, output a single integer representing the number of distinct palindromic substrings in the given string. Each answer should be printed on a separate line.

## sample

3
ababa
abcd
aaa

5
4
3

</p>