题目描述

约19世纪末，在欧州的商店中出售一种智力玩具，在一块铜板上有三根杆 a,b,c，最 a 杆上自上而下、由小到大顺序串着由 n 个圆盘构成的塔。目的是将 a 杆上的盘全部移到 b 杆上，条件是一次只能移动一个盘，且不允许大盘放在小盘的上面。

输入格式

输入为一个整数 n

输出格式

输出将 n 个盘子 从 a 移动到 b 需要的步数。

样例

2

3

3

7