The Four Towers of Hanoi

Time limit3sMemory limit128 MB

Summary

Move all N disks to the last peg with four pegs in the fewest moves and print the count per test case.

Level: Medium7 of 10
Topics: Dynamic programming, Math
Solved: No attempts yet

Problem

The Tower of Hanoi is a well known puzzle. There are 3 pegs and $N$ disks of distinct sizes, stacked on the first peg from the largest at the bottom to the smallest on top. You move one disk at a time, always the topmost disk of some peg, and you never place a larger disk on a smaller one. The goal is to move every disk to the last peg.

This time there are 4 pegs instead of 3. With two spare pegs rather than one, how many moves does it take to relocate all the disks?

Find the minimum number of moves that takes all $N$ disks to the last peg using 4 pegs.

Input

The input has several lines. Each line holds one disk count $N$ ( $1 \le N \le 1000$ ). Read until the end of the input and treat every line as one test case.

Output

For each test case print one line in the form Case i: X, where $i$ is the 1-based test case number and $X$ is the minimum number of moves. The answer fits in a 64-bit integer type such as long long.

Hint

The Tower of Hanoi with 4 or more pegs stayed unsolved for a long time. For 4 pegs it was proved in 2014 that the Frame-Stewart algorithm gives the optimal answer.

Examples1

Example 1
Input
```
1
3
5
```
Expected output
```
Case 1: 1
Case 2: 5
Case 3: 13
```