After losing his match against Sabrina, Chotu now knows that he require a Ghost Pokémon to defeat her.
So chotu goes to Ghost Tower to catch Haunter, a Ghost Pokémon. To enter Ghost Tower, Chotu has to enter a password(which is an integer). But the only thing he found on the gate was a string.

Chotu first tried entering the length of the string, But the gate won't open.
Then he tried entering the number of the subsequences, still no luck :(
Now misty tells him that the password should be the number of palindromic subsequences, as Ghost Pokémon like palindromes.
Unfortunately Chotu is only good for Training Pokémon and not so good in programming. So he turns to you, his best friend, and ask you to calculate the number of palindromic subsequence of given string.

Help him crack the password as fast as possible, and help him defeat Sabrina.

Note :
1) A palindrome is a string that reads same forward and backword.
2) A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.
3) Empty string is also considered as a palindrome.

Input
First line contains T, number of test cases
Each of next T lines contains a single string S, the string that Chotu found on the Ghost tower.

Output
For each Test case, print a single integer, the answer to the problem.

Constraints
1 <= T <= 10
1 <= |S| <= 16