Description

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.

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.

Input

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.

Output

For each test case output in a single line an integer - the number of ways.

Sample

Input

5
BAOBAB
ABA
ABABA
ABBBB
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

Output

22
5
17
16
1073741823

Hint

Note the range of rangle