# Four-Tower Towers of Hanoi

For this problem, we extend the Towers of Hanoi to have four towers and ask the question
“What are the fewest number of moves to solve the Towers of Hanoi problem for a given
*n* if we allow four towers instead of the usual three?” We keep the rules of
trying to move *n* disks from one specified post to another and do not allow a bigger
disk to be put on top of a smaller one. What is new for this problem is to have two spare
posts instead of just one.

For example, to move 3 disks from post *A* to post *D*, we can move disk 1 from
*A* to *B*, disk 2 from *A* to *C*, disk 3 from *A* to D,
disk 2 from *C* to *D*, and disk 1 from *B* to *D*, making a
total of 5 moves.

## Input Specification

Input will be positive integers (*n*), one per line, none being larger than
1 000. For each value of *n*, compute the fewest number of moves for the
four-tower problem. Stop processing at the end of the file. (There is no end-of-data flag.)

## Output Specification

Output the fewest number of moves. Follow this format exactly:
“`Case`

”, one space, the case number, a colon and one space, and the
answer for that case. You may assume the answer will fit in a 64-bit integer type. Do not
print any trailing spaces.

## Sample Input

`1`

`3`

`5`

download as text file
## Output for Sample Input

`Case 1: 1`

`Case 2: 5`

`Case 3: 13`

download as text file