Organize Your Train part II

時間制限 : 1 sec, メモリ制限 : 65536 KB
英語版はこちら

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

Source: ACM International Collegiate Programming Contest , Japan Domestic Contest, Yokohama, Japan, 2006-06-30
http://www.acm-japan.org/icpc2006/