이상한 하노이의 탑

찰리 다크브라운(Charlie Darkbrown)은 또 한 번 지루한 컴퓨터 과학 수업을 듣고 있습니다. 지금 선생님은 표준 하노이의 탑 문제를 설명하고 있는데, 찰리는 지루해서 죽을 지경입니다.

그림: 표준(세 개) 하노이의 탑.

선생님이 칠판을 가리키며 말합니다. "문제는 이렇습니다.

• 세 개의 탑 A, B, C가 있습니다.
• 원판은 $n$개입니다. 퍼즐을 푸는 동안 $n$은 변하지 않습니다.
• 모든 원판의 크기는 서로 다릅니다.
• 처음에 원판들은 탑 A에 위에서 아래로 크기가 커지는 순서로 쌓여 있습니다.
• 목표는 모든 원판을 탑 A에서 탑 C로 옮기는 것입니다.
• 한 번에 원판 하나만, 어떤 탑의 맨 위에서 빈 탑으로, 또는 맨 위 원판이 더 큰 탑 위로 옮길 수 있습니다.

여러분이 할 일은 모든 원판을 탑 A에서 탑 C로 옮기는 데 필요한 최소 이동 횟수를 구하는 것입니다."

찰리: "정말 지루하네요. 이건 간단한 재귀로 풀 수 있다는 걸 누구나 알아요. 이렇게 뻔한 걸 코딩하긴 싫습니다!"

선생님이 한숨을 쉽니다. "좋아, 찰리, 너에게 더 어려운 걸 줘 보자. 네 번째 탑 D를 추가한다. 네 개의 탑을 모두 사용해서 모든 원판을 탑 A에서 탑 D로 옮기는 최소 이동 횟수를 구해라."

찰리는 짜증난 표정입니다. "으윽... 네 개의 탑에 대한 최적 알고리즘은 모르는데..."

사실 문제 해결은 찰리가 잘하는 일이 아닙니다. 찰리가 정말로 잘하는 유일한 것은 일을 대신 해 줄 수 있는 사람 옆에 앉아 있는 것입니다. 그리고 그 사람이 바로 여러분이며, 찰리는 벌써 여러분을 노려보고 있습니다.

다행히 여러분은 $n \le 12$에 대해 다음 알고리즘이 성립한다는 것을 알고 있습니다. 먼저 탑 A에 $k \ge 1$개의 원판을 고정해 두고, 나머지 $n - k$개의 원판을 네 개의 탑 알고리즘을 사용해 탑 A에서 탑 B로 옮깁니다. 그다음 탑 A에 남은 $k$개의 원판을 세 개의 탑 알고리즘을 사용해 탑 D로 옮깁니다. 마지막으로 탑 B에 있는 $n - k$개의 원판을 네 개의 탑 알고리즘을 사용해 탑 D로 옮깁니다(이미 탑 D에 놓인 $k$개의 원판은 건드리지 않습니다). 이것을 모든 $k \in {1, \dots, n}$에 대해 수행하고, 이동 횟수가 가장 적어지는 $k$를 택합니다.

예를 들어 $n = 3$, $k = 2$인 경우, 먼저 $3 - 2 = 1$개의 원판을 네 개의 탑 알고리즘으로 탑 A에서 탑 B로 옮기고(1번 이동), 남은 두 개의 원판을 세 개의 탑 알고리즘으로 탑 A에서 탑 D로 옮기며(3번 이동), 마지막으로 탑 B의 원판 하나를 네 개의 탑 알고리즘으로 탑 D로 옮깁니다(1번 이동). 따라서 $n = 3$, $k = 2$일 때는 $5$번 이동합니다. 나머지 값 $k = 1$과 $k = 3$을 확인해 보면 $5$가 실제로 최적임을 알 수 있습니다.

정수 $n$ ($1 \le n \le 12$) 하나가 한 줄에 주어집니다. $n$은 원판의 개수입니다.

네 개의 탑을 모두 사용해 원판 $n$개를 탑 A에서 탑 D로 옮기는 데 필요한 최소 이동 횟수를 한 줄에 출력합니다.