Problems
Four-Tower Towers of Hanoi
Four-Tower Towers of Hanoi
Refer to problem three for a description of the classic three-tower version of the Towers of Hanoi problem.
For this problem, we extend the Towers of Hanoi to have four towers and ask the question "\textit{What are the fewest number of moves to solve the Towers of Hanoi problem for a given }\textit{\textbf{n}}\textit{ if we allow four towers instead of the usual three?}" We keep the rules of trying to move \textbf{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 \textbf{3} disks from post \textbf{A} to post \textbf{D}, we can move disk \textbf{1} from \textbf{A} to \textbf{B}, disk \textbf{2} from \textbf{A} to \textbf{C}, disk \textbf{3 }from \textbf{A} to \textbf{D}, disk \textbf{2} from \textbf{C} to \textbf{D}, and disk \textbf{1} from \textbf{B} to \textbf{D}, making a total of \textbf{5} moves.
\InputFile
Input will be positive integers (\textbf{n}), one per line, none being larger than \textbf{1000}. For each value of \textbf{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.)
\OutputFile
Output the fewest number of moves. Follow this format exactly: "\textbf{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 \textbf{64}-bit integer type. Do not print any trailing spaces.
Input example #1
1 3 5
Output example #1
Case 1: 1 Case 2: 5 Case 3: 13