새로운 하노이 탑

새로운 하노이 탑 게임의 규칙은 다음과 같다.

막대는 A, B, C 세 개다.
게임이 시작될 때 각 막대에는 원판이 0개 이상 놓여 있다.
원판의 크기는 모두 같고, 원판의 종류도 A, B, C 세 가지다. 종류가 A인 원판을 원판 A라고 부르고, 나머지 두 종류도 같은 방식으로 부른다.
한 번 움직이는 것은 한 막대의 맨 위 원판을 다른 막대의 맨 위로 옮기는 것이다.
게임의 목표는 막대 A에 원판 A만, 막대 B에 원판 B만, 막대 C에 원판 C만 놓이게 하는 것이다.

세 막대에 놓인 원판의 처음 상태가 주어졌을 때, 목표를 달성하는 데 필요한 최소 움직임 횟수를 구하는 프로그램을 작성하시오.

첫째 줄에 막대 A에 놓인 원판의 개수와 막대 A의 상태, 둘째 줄에 막대 B에 놓인 원판의 개수와 막대 B의 상태, 셋째 줄에 막대 C에 놓인 원판의 개수와 막대 C의 상태가 주어진다.

막대의 상태는 맨 아래 원판부터 차례로 적은 문자열이며, A, B, C로만 이루어진다. 원판이 하나도 없는 막대는 개수 0만 주어지고 뒤에 문자열이 붙지 않는다. 세 막대에 놓인 원판 개수의 합은 1보다 크거나 같고 10보다 작거나 같다.

목표를 달성하는 데 필요한 최소 움직임 횟수를 한 줄에 출력한다.

막대 A에 원판 B, 막대 B에 원판 C, 막대 C에 원판 A가 하나씩 놓인 상태는 다섯 번 만에 끝난다.

막대 A에 아래에서부터 원판 C, 원판 B, 원판 A가 놓이고 나머지 두 막대가 비어 있는 상태도 다섯 번이면 끝난다.