Palindromes

A palindrome is a sequence of one or more characters that reads the same 
from the left as it does from the right. For example, Z, TOT and MADAM 
are palindromes, but ADAM is not.

You are given a sequence S of N capital latin letters.  How many ways can 
one cross out some symbols (maybe 0) so that the rest of sequence becomes 
a palidrome?  Variants that differ only in the order of crossing out 
should be considered the same.

Input

The input file contains several test cases. The first line contains an 
integer T that indicates how many test cases are to follow.

Each of the T lines contains a sequence S (1 <= N <= 60) of capital 
letters.
 
Output

For each test case S output in a single line an integer, the number of 
ways to cross out characters of S to obtain a palindrome.


Sample Input

3
BAOBAB
AAAA
ABA

Output for Sample Input

22
15
5