세계의 종말

전설에 따르면, 거대한 하노이의 탑 퍼즐을 풀고 있는 수도승 무리가 있다. 하노이의 탑은 잘 알려진 퍼즐로, 세 개의 기둥과 서로 크기가 다른 원반들로 이루어져 있다. 처음에는 모든 원반이 한 기둥에 쌓여 있으며, 아래에서 위로 갈수록 작아지도록(가장 큰 원반이 맨 아래, 가장 작은 원반이 맨 위) 정렬되어 있다. 목표는 다음 두 규칙을 지키면서 이 원반 더미를 다른 기둥으로 옮기는 것이다.

1. 한 번에 원반 하나만 옮길 수 있다.
2. 어떤 기둥에 이미 더 작은 원반이 놓여 있다면, 그 위에 더 큰 원반을 올릴 수 없다.

수도승들은 퍼즐을 다 풀면 세계가 종말을 맞는다고 믿는다. 그들이 지금까지 얼마나 진행했는지 안다고 하자. 수도승들이 가장 효율적인(최소 이동 횟수의) 방법으로 퍼즐을 풀고 있다고 가정할 때, 세계에는 얼마의 시간이 남아 있는가?

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 한 줄에 주어지는 길이 1 이상 63 이하의 문자열이다. 이 문자열은 대문자 A, B, C로만 이루어진다. 문자열의 길이는 원반의 개수를 나타내고, 각 문자는 원반 하나의 현재 위치를 나타낸다. 첫 번째 문자는 가장 작은 원반의 위치, 두 번째 문자는 두 번째로 작은 원반의 위치이며, 이런 식으로 마지막 문자는 가장 큰 원반의 위치를 나타낸다. 각 문자는 A, B, C 중 하나로, 해당 원반이 현재 놓여 있는 기둥을 뜻한다. 수도승들의 최종 목표는 모든 원반을 기둥 A에서 기둥 B로 옮기는 것이며, 입력은 항상 최적해(최소 이동) 과정 중에 실제로 나타나는 올바른 상태임이 보장된다. 입력의 끝은 대문자 X 하나만 있는 줄로 표시된다.

각 테스트 케이스마다, 주어진 하노이의 탑 상태에서 퍼즐이 완성될 때까지 남은 이동 횟수를 한 줄에 하나씩 출력한다. 불필요한 공백을 출력하지 말고, 답 사이에 빈 줄을 넣지 마라. 가능한 모든 입력에 대한 답은 부호 있는 64비트 정수 범위 안에 들어간다.