题目描述

有四座塔，分别记为 A、B、C、D。
共有 n 个尺寸互不相等的圆盘，初始时全部按尺寸从大到小（塔底→塔顶）叠放在塔 A 上。
目标是把所有圆盘移动到塔 D。

每次只能移动一个圆盘，且移动时必须满足：

• 目标塔为空，或者
• 目标塔顶部圆盘的尺寸 大于 被移动圆盘的尺寸。

求完成该任务所需的最少移动步数。

输入格式

无输入。

输出格式

对于每个整数 n（1 ≤ n ≤ 12），输出一行，表示对应 n 的最小移动步数。

数据范围

1 ≤ n ≤ 12

输入样例

参照题意

输出样例