하노이의 탑이라는 유명한 문제가 있다.

하지만 이 문제는 너무 유명한 나머지 이제는 식상하다.

그러니까 이번엔 탑을 3개가 아닌 4개로 늘려서 생각해보자!

N개의 원판과 4개의 막대가 있을 때, 즉 보조 막대가 한 개가 아닌 두 개이면 몇 번 움직여서 모든 원판을 끝의 원판으로 옮길 수 있을까?

4개의 막대를 이용해서 N개의 원판을 모두 옮기기 위한 최소 이동 횟수를 구해보자.

입력 형식

각 줄에 원판의 개수 N(1 ≤ N ≤ 1000)이 주어진다.

출력 형식

테스트 케이스와 함께 답을 출력한다(단, 답은 64-bit 정수 타입(e.g. long long)으로 표현 가능하다).

예제 입력

1
3
5

예제 출력

Case 1: 1
Case 2: 5
Case 3: 13

힌트

사실 막대가 4개 이상인 하노이의 탑 문제는 Open Problem이므로 이 답이 최적이라는 보장은 없다 :(

하지만, 2014년에 Frame–Stewart algorithm이 최적해를 준다는 것이 증명되었다.