Sinulle on annettu merkkijono, jossa on n merkkiä. Monellako tavalla voit järjestää merkit niin, että tuloksena on palindromi?

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku t: testien määrä.

Tämän jälkeen syötteessä on t riviä, joista jokainen sisältää yhden merkkijonon. Merkkijonossa on n merkkiä, ja jokainen merkki on väliltä a..z.

Tuloste

Ohjelmasi tulee tulostaa jokaista testiä kohden yksi kokonaisluku: mahdollisten palindromien määrä.

Rajat

• 1 \le t \le 100
• 1 \le n \le 40

Esimerkki

Syöte:

3
aabbc
abcd
xxxxxx

Tuloste:

2
0
1