The Priest Mathematician

"하노이의 탑(Tower of Hanoi)" 퍼즐에 관한 고대 신화는 이미 잘 알려져 있다. 최근 밝혀진 전설에 의하면, 브라흐마나 수도사들이 64개의 원반을 한 쪽 침에서 다른 쪽 침으로 옮기는 데 얼마나 오래 걸리는지를 알아내고 나서는 더 빠르게 옮기는 방법을 찾아내자는 결론을 내렸다. 다음 그림은 침이 네 개인 하노이의 탑이다.
http://online-judge.uva.es/p/v102/p10254b.jpg
사원에 있는 수도사 중 한 명이 동료 수도사에게 침을 하나만 추가하면 1초에 원반을 하나씩 옮긴다고 할 때 한 나절이면 모든 원반을 옮길 수 있을 것이라고 알려주었다. 그가 제안한 방법은 다음과 같다.
{{|
1. 맨 위에 있는 원반(맨 위에 있는 k개의 원반)을 다른 침으로 옮긴다.
2. 침이 세 개 있는 경우에 쓰는 방법을 그대로 적용해서 나머지 n-k개의 원반(전체 원반의 개수를 n개라고 가정)을 목표 지점으로 옮긴다.
3. 마지막으로 네 개의 침을 이용해서 맨 위에 있던 k개의 원반을 최종 목적지로 옮긴다.
|}}
이동 횟수를 최소화할 수 있는 k값을 계산한 다음 18,433번만 옮기면 된다는 결론을 내렸다. 따라서 침이 세 개만 있을 때는 5천억년이 걸릴 일을 침 하나만 추가하면 5시간 7분 13초만에 할 수 있다는 것을 알아냈다.
그 영리한 수도사가 제안한 네 개의 침을 사용하는 방법으로 원반을 옮기는 횟수를 계산하자. 원반은 한 번에 하나씩만 옮길 수 있으며 큰 원반을 작은 원반 위에 놓을 수는 없다. 이동 횟수를 구하려면 먼저 원반 이동 횟수를 최소화시킬 수 있는 k값을 구해야 한다.

입력 파일은 여러 줄로 구성된다. 각 줄에는 0 이상 10,000 이하의 정수 N이 들어있으며, 이 값은 옮겨야 할 원반의 개수를 나타낸다. 파일 끝 문자가 들어오면 입력이 종료된다.

입력된 각 줄에 대해 N개의 원반을 최종 위치로 옮기는 데 필요한 이동 횟수를 출력한다.

{{| 1
2
28
64 |}}

{{| 1
3
769
18433 |}}

----
문제분류 경시대회준비반