Problem B: 列車の編成パートII

日本の鉄道会社RJ貨物は，横浜羽沢に操車場を完成させた．操車場の配線を図B-1に示す．

図 B-1: 操車場の配線

貨物列車は2両以上72両以下の貨車を連結している．貨車の種類は26あり，その種類をa〜zの英小文字1文字で表す．同じ種類の貨車同士は互いに区別されず，また個々の貨車の向きも区別されない．したがって，2文字以上72文字以下の英小文字の並びで1つの列車の編成が完全に表せる．

操車場に到着した列車は， (storage linesに入る直前に)任意の連結箇所で2つに分割される．続いてそれぞれの部分は，その必要があれば(reversal lineを使って)前後反転される．最後にこれら2つの部分を任意の順序で再び連結することで，最終的な編成を作る．前後反転は，部分ごとに行っても行わなくてもよい．

たとえば，到着時の編成が「abcd」のとき，編成の分割のしかたは3:1，2:2，1:3のいずれかである．分割のしかたそれぞれについて，構成可能な最終編成は次のようになる(「+」は最後の連結位置を示す):

  [3:1]
    abc+d  cba+d  d+abc  d+cba
  [2:2]
    ab+cd  ab+dc  ba+cd  ba+dc  cd+ab  cd+ba  dc+ab  dc+ba
  [1:3]
    a+bcd  a+dcb  bcd+a  dcb+a

重複を除いて数えると，12種類の編成が作り出せることになる．

到着した列車の編成が与えられたとき，上記の操車場によって構成可能な，互いに異なる編成の数を回答せよ．

Input

入力全体は以下の形式をしている．

データセット数 = m
データセット1
データセット2
...
データセットm

各データセットは入場してくる列車を表す， 2個以上72個以下の英小文字のみを含む1行の文字列である．

Output

各データセットについて，編成可能な列車の種類数をそれぞれ1行として出力しなさい．出力は他の文字を含んではならない．

Sample Input

4
aa
abba
abcd
abcde

Output for the Sample Input

1
6
12
18

---