Torres de Hanói

As Torres de Hanoi são um quebra-cabeca muito antigo e conhecido. Ele é constituído de um conjunto de N discos de tamanhos diferentes e três pinos verticais, nos quais os discos podem ser encaixados.

Cada pino pode conter uma pilha com qualquer número de discos, desde que cada disco não seja colocado acima de outro disco de menor tamanho. A configuracão inicial consiste de todos os discos no pino 1. O objetivo é mover todos os discos para um dos outros discos, sempre obedecendo à restricão de não colocar um disco sobre outro menor.

Um algoritmo para resolver este problema é o seguinte.

procedimento Hanoi(N, Orig, Dest, Temp)
  se N = 1 então
    mover o menor disco do pino Orig para o pino Dest;
  senão
    Hanoi(N-1, Orig, Temp, Dest); 
    mover o N-ésimo menor disco do pino Orig para o pino Dest;
    Hanoi(N-1, Temp, Dest, Orig);
  fim-se
fim

Tarefa

Sua tarefa é escrever um programa que determine quantos movimentos de trocar um disco de um pino para outro serão executados pelo algoritmo acima para resolver o quebra-cabeca.

Entrada

A entrada possui vários conjuntos de teste. Cada conjunto de teste é composto por uma única linha, que contém um único número inteiro N (0 ≤ N ≤ 30), indicando o número de discos. O final da entrada é indicado por N = 0.

Exemplo de Entrada

1
2
0

Saída

Para cada conjunto de teste, o seu programa deve escrever três linhas na saída. A primeira linha deve conter um identificador do conjunto de teste, no formato "Teste n", onde n é numerado seqüencialmente a partir de 1. A segunda linha deve conter o número de movimentos que são executados pelo algoritmo dado para resolver o problema das Torres de Hanoi com N discos. A terceira linha deve ser deixada em branco. A grafia mostrada no Exemplo de Saída, abaixo, deve ser seguida rigorosamente.

Exemplo de Saída

Teste 1
1

Teste 2
3

(esta saída corresponde ao exemplo de entrada acima)

Restricões

0 ≤ N ≤ 30 (N = 0 apenas para indicar o final da entrada)