题目描述

汉诺塔（又称河内塔）问题是印度的一个古老传说。

有三根杆子 $A$、$B$、$C$。$A$ 杆上有若干个大小不同的圆盘，最大的圆盘在最下面，其余圆盘按照大小依次叠放在上面。

游戏规则如下：

1. 每次只能移动一个圆盘；
2. 圆盘只能从一根杆移动到另一根杆；
3. 小圆盘只能放在大圆盘上面，不能出现大圆盘放在小圆盘上面的情况；
4. 需要将 $A$ 杆上的所有圆盘移动到 $C$ 杆。

请输出移动圆盘的最少步骤。

汉诺塔问题的递归思路如下：

1. 如果只有一个圆盘，则直接将圆盘从源杆移动到目标杆；

2. 如果有 $n$ 个圆盘：

   • 先将前 $n-1$ 个圆盘从源杆移动到辅助杆；
   • 再将第 $n$ 个圆盘从源杆移动到目标杆；
   • 最后将前 $n-1$ 个圆盘从辅助杆移动到目标杆。

输入格式

输入一个整数 $N$，表示 $A$ 杆上圆盘的数量。

输出格式

输出若干行，每行表示一次移动操作。

格式为：

源杆 To 目标杆

样例

3

A To C
A To B
C To B
A To C
B To A
B To C
A To C

数据范围

$0 < N \le 10$。