题目描述

有三根杆子 A，B，C。A 杆上有 N 个（N > 1）穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至 C 杆：

• 每次只能移动一个圆盘；
• 大盘不能叠在小盘上面。

提示：可将圆盘临时置于 B 杆，也可将从 A 杆移出的圆盘重新移回 A 杆，但都必须遵循上述两条规则。

问：如何移动？最少要移动多少次？

输入格式

输入一个整数 n（1 ≤ n < 63），表示圆盘的个数。

输出格式

输出最少的移动次数。

输入样例 #1

1

输出样例 #1

1

输入样例 #2

2

输出样例 #2

3