Towers of Hanoi
By OBI - Olimpíada Brasileira de Informática 2003 
Brazil
By OBI - Olimpíada Brasileira de Informática 2003 Brazil
The puzzle Towers of Hanoi is very old and known, consisting of a set of N disks of different sizes and three vertical pins, in which the disks can be fitted.
Each pin may contain a stack with any number of disks, since each disk is not placed above the other smaller sized disc. The initial configuration consists of all disks on pin 1. The aim of the puzzle is to move all disks to one of the other pins, always obeying the restriction not put a disc on another smaller.
An algorithm to solve this problem is the following.
procedure Hanoi(N, Orig, Dest, Temp)
if N = 1 so
move the smaller disc Orig pin for pin Dest;
if no
Hanoi(N-1, Orig, Temp, Dest);
moving the Nth lower disc Src Dest pin for pin;
Hanoi(N-1, Temp, Dest, Orig);
end-if
end
Your task is to write a program to determine how many moves to change a disk from a pin to the other will be executed by the above algorithm to solve the puzzle.
The input has multiple test sets. Each test set consists of a single line containing a single integer N (0 ≤ N ≤ 30), indicating the number of disks. The end of input is indicated by N = 0.
For each test set, your program must write three lines in the output. The first line should contain a test set identifier in the format "Teste n", where n is sequentially numbered from 1. The second line should contain the number of movements that are performed by the given algorithm to solve the problem of Torres Hanoi with N disks. The third line should be left blank. The spelling shown in Example output below should be followed strictly.
| Input Sample | Output Sample |
|
1 2 0 |
Teste 1 1 Teste 2 3 |