열차 재구성 II
시간 제한1초메모리 제한128 MB
입력 문자열을 임의의 위치에서 두 부분으로 나누고, 각 부분을 선택적으로 뒤집은 뒤 두 부분을 임의의 순서로 이어 붙여 만들 수 있는 서로 다른 문자열의 개수를 센다.
문제
일본의 화물 철도 회사 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가지입니다.
도착 구성이 주어질 때, 위에서 설명한 입환선으로 만들 수 있는 서로 다른 구성의 개수를 구하세요.
입력
첫 번째 줄에 데이터셋의 개수 이 주어집니다. 이어지는 개의 줄에는 각각 하나의 데이터셋이 주어지며, 도착하는 열차를 나타내는 길이 2 이상 72 이하의 소문자 문자열입니다.
출력
각 데이터셋에 대해, 만들 수 있는 서로 다른 열차 구성의 개수를 한 줄에 하나씩 출력하세요. 그 밖의 문자는 출력하지 않습니다.