#描述#
Palindromes date back at least to 79 AD, as the palindromic Latin word square
"Sator Arepo Tenet Opera Rotas" (The sower, Arepo, holds works wheels) was
found as a graffito at Herculaneum, buried by ash in that year. This palindrome
is remarkable for the fact that it also reproduces itself if one forms a word from
the first letters, then the second letters and so forth. Hence, it can be arranged
into a word square that reads in four different ways: horizontally or vertically
from either top left to bottom right or bottom right to top left.
<br />
Now,Given a sequence S of N capital latin letters. How many ways can one score
out a few symbols (maybe 0) that the rest of sequence become a palindrome.
Variants that are only different by an order of scoring out should be considered
the same.<br />

#格式#
##输入格式##
The input file contains several test cases (less than 15). 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). So actually each of
these lines is a test case.

##输出格式##
For each test case output in a single line an integer - the number of ways.

#样例1#
##样例输入1##

5
BAOBAB
ABA
ABABA
ABBBB
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

##样例输出1##

22
5
17
16
1073741823

#限制#
1000ms
32768KB

#提示#
Note the range of rangle

#来源#