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