说明

      经典的汉诺塔问题经常作为一个递归的经典例题存在。可能有人并不知道汉诺塔问题的典故。汉诺塔来源于印度传说的一个故事，上帝创造世界时作了三根金刚石柱 子，在一根柱子上从下往上按大小顺序摞着64片黄金圆盘。上帝命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放 大圆盘，在三根柱子之间一回只能移动一个圆盘。有预言说，这件事完成时宇宙会在一瞬间闪电式毁灭。也有人相信婆罗门至今仍在一刻不停地搬动着圆盘。恩，当 然这个传说并不可信，如今汉诺塔更多的是作为一个玩具存在。Gardon就收到了一个汉诺塔玩具作为生日礼物。

　　Gardon很想知道在一次游戏中使用了N个盘子时，他需要多少次移动才能把他们都 移到第三个柱子上？

输入格式

包含多组数据，每个数据一行，是盘子的数目N(1<=N<=64)。

（VC也用unsigned __int64,  g++与dev c用到unsigned long long）

输出格式

对于每组数据，输出一个数，到达目标需要的最少的移动数。

1
3

1
7

来源

数学建模-递推与递归