Strange Towers of Hanoi

Charlie Darkbrown is sitting through yet another boring Computer Science lesson. Right now the teacher is explaining the standard Tower of Hanoi problem, which bores Charlie to death.

Figure: The standard (three) Towers of Hanoi.

The teacher points at the blackboard and says: "Here is the problem.

• There are three towers: A, B and C.
• There are $n$ disks. The number $n$ stays constant while solving the puzzle.
• All disks have different sizes.
• Initially the disks are stacked on tower A, increasing in size from the top to the bottom.
• The goal is to move all of the disks from tower A to tower C.
• One disk at a time may be moved from the top of a tower onto an empty tower, or onto a tower whose top disk is larger.

Your task is to compute the smallest number of moves needed to move every disk from tower A to tower C."

Charlie: "This is incredibly boring — everyone knows this can be solved with a simple recursion. I refuse to code something this trivial!"

The teacher sighs: "Fine, Charlie, let us find something harder for you. You get a fourth tower D. Compute the smallest number of moves needed to move all of the disks from tower A to tower D using all four towers."

Charlie looks annoyed: "Ugh... I do not know an optimal algorithm for four towers..."

The real trouble is that problem solving is not one of Charlie's strengths. The one thing Charlie is truly good at is sitting next to someone who can do the work — and you are that someone. He is already glaring at you.

Luckily you know that the following algorithm works for $n \le 12$. First, $k \ge 1$ disks are kept fixed on tower A and the remaining $n - k$ disks are moved from tower A to tower B using the four-tower algorithm. Then the $k$ disks on tower A are moved to tower D using the three-tower algorithm. Finally the $n - k$ disks on tower B are moved to tower D using the four-tower algorithm (without disturbing the $k$ disks already on tower D). Do this for every $k \in {1, \dots, n}$ and take the value of $k$ that yields the fewest moves.

For example, with $n = 3$ and $k = 2$ you first move $3 - 2 = 1$ disk from tower A to tower B using the four-tower algorithm (one move), then move the remaining two disks from tower A to tower D using the three-tower algorithm (three moves), and finally move the single disk from tower B to tower D using the four-tower algorithm (one more move). So $n = 3$ with $k = 2$ costs $5$ moves. Checking the other values $k = 1$ and $k = 3$ confirms that $5$ is indeed optimal.

A single line containing one integer $n$ ($1 \le n \le 12$), the number of disks.

Print a single line containing the minimum number of moves needed to move all $n$ disks from tower A to tower D using all four towers.