하노이의 네 탑

하노이의 탑은 잘 알려진 문제다. 막대 3개와 크기가 모두 다른 원판 $N$개가 있고, 원판은 큰 것부터 작은 것 순서로 첫 번째 막대에 쌓여 있다. 한 번에 어느 한 막대의 맨 위 원판 하나만 다른 막대로 옮길 수 있고, 큰 원판을 작은 원판 위에 올릴 수는 없다. 이 규칙을 지키면서 원판을 모두 마지막 막대로 옮기는 것이 목표다.

이번에는 막대를 3개가 아니라 4개로 늘린다. 보조 막대가 한 개가 아니라 두 개라면 원판을 모두 옮기는 데 몇 번이 필요할까?

막대 4개를 써서 원판 $N$개를 모두 마지막 막대로 옮기는 최소 이동 횟수를 구하라.

입력은 여러 줄로 이루어진다. 각 줄에 원판의 개수 $N$($1 \le N \le 1000$)이 하나씩 주어진다. 입력이 끝날 때까지 각 줄을 테스트 케이스 하나로 처리한다.

각 테스트 케이스마다 한 줄에 Case i: X 형식으로 출력한다. $i$는 1부터 시작하는 테스트 케이스 번호이고, $X$는 최소 이동 횟수다. 답은 64비트 정수 타입(예: long long)으로 표현할 수 있다.

막대가 4개 이상인 하노이의 탑은 오랫동안 미해결 문제였다. 막대가 4개인 경우는 2014년에 Frame-Stewart 알고리즘이 최적해를 준다는 것이 증명됐다.