Two-Colored Towers of Hanoi

The Towers of Hanoi is a classic puzzle in which disks are threaded onto pegs. You are given $n$ disks with diameters $1, 2, \dots, n$ and three pegs called $A$, $B$, and $C$. Each disk has a hole in its center so it can be slipped onto a peg. Initially every disk is on peg $A$, stacked from the largest at the bottom to the smallest at the top.

In the original puzzle you move all disks onto one of the free pegs (say $B$) under these rules:

• in a single move you may take the top disk of one peg and place it on top of another peg;
• on every peg the order must always be preserved: larger disks below, smaller disks above.

The disks stacked on one peg form a tower. In summary:

• you cannot pull a disk out of the middle of a tower, nor insert a disk into the middle of a tower;
• you may not move more than one disk at a time;
• you may not place a larger disk on top of a smaller one.

The goal of the original puzzle is to move the whole tower from one peg to another in the fewest possible moves.

The two-colored Towers of Hanoi is a slightly modified version. As before there are three pegs and $n$ disks with diameters $1, 2, \dots, n$. This time, however, disks with odd diameters ($1, 3, 5, \dots$) are white and disks with even diameters ($2, 4, 6, \dots$) are black. The goal is to move, following the rules above, all white disks onto peg $B$ and all black disks onto peg $C$.

Write a program that computes the minimum number of moves needed to gather the white disks on peg $B$ and the black disks on peg $C$.

The first line of standard input contains a single integer $n$ ($0 \le n \le 1000$), the number of disks.

Print to standard output a single integer: the minimum number of moves needed to separate the white and black disks.