Again 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.

Given a sequence S of N capital latin letters, you are to determine how many ways one can score out a few symbols (maybe 0) so that the rest of the sequence becomes a palindrome. Varints that are only different in the order of scoring out should be considered the same.

Input Specification

The input 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 next T lines contains a sequence S (1 ≤ N ≤ 60). So actually, each of these lines is a test case.

Output Specification

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

Sample Input

1. 3
2. BAOBAB
3. AAAA
4. ABA

download as text file

Output for Sample Input

1. 22
2. 15
3. 5

download as text file