Unique Palindromic Substrings Counting

You are given a string, and your task is to count the number of unique palindromic substrings in it. A substring is defined as a contiguous sequence of characters within the string. A palindrome is a string that reads the same forward and backward. Note that every single character is also considered a palindrome.

For example, in the string abba, the unique palindromic substrings are a, b, bb, and abba, resulting in a count of 4. You will be provided with multiple test cases. Your program should read from standard input and write the result for each test case to standard output.

inputFormat

The first line of input contains a single integer T (the number of test cases). Each of the following T lines contains a single string S for which you must determine the number of unique palindromic substrings.

outputFormat

For each test case, output a single line containing the count of unique palindromic substrings for the corresponding string.## sample

2
a
b

1
1