열차 재구성 II

일본의 화물 철도 회사 RJ Freight는 최근 요코하마 하자와(Hazawa)에 입환선(교환선)을 건설했습니다. 선로 배치는 그림 B-1과 같습니다.

그림 B-1: 입환선의 배치

한 화물 열차는 2량에서 72량까지의 화차로 이루어집니다. 화차의 종류는 26가지이며, 각각 소문자 a부터 z까지로 나타냅니다. 같은 종류의 화차는 서로 구별할 수 없고, 화차의 방향도 의미가 없습니다. 따라서 길이가 2 이상 72 이하인 소문자 문자열 하나로 열차의 구성을 완전히 표현할 수 있습니다.

입환선에 도착한 열차는 (측선에 들어가기 전) 임의의 위치에서 두 개의 부분 열차로 나뉩니다. 각 부분 열차는 반전선을 이용해 방향을 뒤집을 수 있습니다(선택 사항). 마지막으로 두 부분 열차를 둘 중 어느 순서로든 연결하여 최종 구성을 만듭니다. 반전은 각 부분 열차마다 독립적으로 선택할 수 있습니다.

예를 들어 도착 구성이 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가지입니다.

도착 구성이 주어질 때, 위에서 설명한 입환선으로 만들 수 있는 서로 다른 구성의 개수를 구하세요.

첫 번째 줄에 데이터셋의 개수 $m$이 주어집니다. 이어지는 $m$개의 줄에는 각각 하나의 데이터셋이 주어지며, 도착하는 열차를 나타내는 길이 2 이상 72 이하의 소문자 문자열입니다.

각 데이터셋에 대해, 만들 수 있는 서로 다른 열차 구성의 개수를 한 줄에 하나씩 출력하세요. 그 밖의 문자는 출력하지 않습니다.