Distinct Palindromic Substrings

You are given a string \(S\). Your task is to determine the number of distinct palindromic substrings contained in \(S\).

A substring is a contiguous sequence of characters within the string. A palindrome is a string that reads the same forward and backward. Formally, for a substring \(s\) extracted from \(S\), it is a palindrome if \(s = s^R\), where \(s^R\) is the reversal of \(s\).

Example:
For \(S = \texttt{aabaa}\), the distinct palindromic substrings are: \(\{a, aa, aba, aabaa, b\}\). Thus, the answer is 5.

You need to process multiple test cases.

inputFormat

The first line contains an integer \(T\) (\(1 \le T \le 100\)) representing the number of test cases. Each of the following \(T\) lines contains a non-empty string \(S\) consisting of lowercase English letters.

\(S\) is guaranteed to be of manageable length so that a solution with a nested loop checking all substrings is feasible.

outputFormat

For each test case, output a single integer on a new line representing the number of distinct palindromic substrings in the corresponding string.

## sample

3
aabaa
abcd
aaa

5
4
3

</p>