TopCoder

Thumb skin by baishetirryna
joylintp
<( _ _ )>

User's AC Ratio

85.7% (18/21)

Submission's AC Ratio

41.2% (35/85)

Description

所謂的「迴文」,就是指一個字串從頭開始唸跟倒著唸結果完全一樣。例如abccaaccba就是一個迴文字。

而所謂的「全排列」,則是指一個字串裡的每個字母在經過順序的調換以後所能得到的各種排列。例如abcd的全排列就是:
abcd abdc acbd acdb adbc adcb
bacd badc bcad bcda bdac bdca
cabd cadb cbad cbda cdab cdba
dabc dacb dbac dbca dcab dcba

請寫出一個程式,對於輸入的字串,算出在這個字串的全排列裡有多少個是迴文。例如aabb的全排列為:
aabb abab abba baab baba bbaa
其中abba和baab是迴文,因此aabb的全排列裡有2個迴文。

Input Format

輸入檔第一行是一個整數 N (1 ≤ N ≤ 50) 代表題目的數目。接下來N行輸入,每一行會有一個長度不超過40的字串,這個字串會完全由小寫的英文字母構成。﹝字串的長度最少是1﹞

Output Format

對每一行字串,請在每行輸出這個字串的全排列裡有幾個迴文﹝如果全排列裡一個迴文都沒有的話,就輸出0﹞。輸出的數字不會超過long long int的大小。

Sample Input

3
aabb
a
abc

Sample Output

2
1
0

Hints

Problem Source

原TIOJ1431 / NPSC2004初賽(prob A)

Subtasks

For Testdata: 0 ~ 0, Score: 100
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 262144