루빅스 큐브의 주기

루빅스 큐브는 여섯 면이 각각 아홉 장의 스티커로 덮여 있는 입체 퍼즐이다. 스티커 색은 파랑, 노랑, 주황, 하양, 초록, 빨강 여섯 가지이고, 처음 상태에서는 한 면의 아홉 장이 모두 같은 색이다. 큐브 안의 회전 장치 덕분에 각 면을 따로 돌릴 수 있어서 면에 붙은 스티커 색이 섞인다.

여섯 면은 아래 그림처럼 F, B, U, D, L, R로 나타낸다. F는 앞면, B는 뒷면, U는 위쪽 면, D는 아래쪽 면, L은 왼쪽 면, R은 오른쪽 면이다.

한 면을 돌리는 것을 이동 한 번이라고 한다. 이동은 그 면을 나타내는 글자로 적는다.

• 대문자는 그 면을 시계 방향으로 90도 돌린다.
• 소문자는 그 면을 반시계 방향으로 90도 돌린다.

방향은 큐브 바깥에서 그 면을 정면으로 바라본 기준이다. 예를 들어 F는 F면을 시계 방향으로 90도 돌리고, r은 R면을 반시계 방향으로 90도 돌린다. 이동을 여러 개 이어 쓴 글자열을 이동 순서열이라고 하며, 왼쪽부터 차례로 적용한다. 따라서 rDF는 R면을 반시계 방향으로 90도 돌린 다음, D면을 시계 방향으로 90도 돌리고, 마지막으로 F면을 시계 방향으로 90도 돌린다.

루빅스 큐브에는 다음 성질이 있다. 어떤 이동 순서열이든 반복해서 적용하면 큐브는 첫 적용 이전의 상태로 돌아온다. 예를 들어 순서열 B를 네 번 적용하면 큐브는 그 상태로 돌아온다.

이동 순서열이 주어졌을 때, 큐브가 처음 상태로 돌아오려면 그 순서열을 최소 몇 번 온전히 적용해야 하는지 구하는 프로그램을 작성하시오.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 한 줄이고, 이동 순서열 하나가 주어진다. 입력은 파일의 끝에서 끝난다.

제한

• 각 순서열의 이동 개수는 1개 이상 80개 이하이다.
• 각 순서열은 F, B, U, D, L, R, f, b, u, d, l, r 열두 글자로만 이루어진다.

각 테스트 케이스마다 한 줄에 정수 하나를 출력한다. 큐브가 처음 상태로 돌아오기까지 그 이동 순서열을 온전히 적용해야 하는 최소 횟수이다.