Count Distinct Palindromic Substrings

Given a string s, your task is to count the number of distinct palindromic substrings present in s. A substring is a contiguous sequence of characters in the string, and a palindrome is a string that reads the same forward and backward.

For instance, given s = "ababa", the distinct palindromic substrings are: a, b, aba, bab and ababa, for a total of 5.

If the input string is empty, the output should be 0.

inputFormat

The first line contains an integer T which represents the number of test cases. Each of the following T lines contains a single string s.

T
s[1]
s[2]
...
s[T]

outputFormat

For each test case, print a single integer on a new line that denotes the number of distinct palindromic substrings of the input string.

## sample

3
a
ababa
aaaa

1
5
4

</p>