题目描述

汉诺塔问题：输入汉诺塔层数n，输出移动步骤。汉诺塔的算法思路： 如果只有一个圆盘，则把该圆盘从A柱到C柱，结束。 如果有n个圆盘，则把前n-1个圆盘移动到B，然后把自己移动到C，最后再把前n-1个移动到C。

输入格式

一个整数n，表示A柱上有n个圆盘（0<n<=10）

输出格式

若干行，一行是一次移动步骤

样例

输入样例 1

2

输出样例 1

输入汉诺塔的层数:
A To B
A To C
B To C

输入样例 2

6

输出样例 2

输入汉诺塔的层数:
A To B
A To C
B To C
A To B
C To A
C To B
A To B
A To C
B To C
B To A
C To A
B To C
A To B
A To C
B To C
A To B
C To A
C To B
A To B
C To A
B To C
B To A
C To A
C To B
A To B
A To C
B To C
A To B
C To A
C To B
A To B
A To C
B To C
B To A
C To A
B To C
A To B
A To C
B To C
B To A
C To A
C To B
A To B
C To A
B To C
B To A
C To A
B To C
A To B
A To C
B To C
A To B
C To A
C To B
A To B
A To C
B To C
B To A
C To A
B To C
A To B
A To C
B To C

输入样例 3

9

输出样例 3

输入汉诺塔的层数:
A To C
A To B
C To B
A To C
B To A
B To C
A To C
A To B
C To B
C To A
B To A
C To B
A To C
A To B
C To B
A To C
B To A
B To C
A To C
B To A
C To B
C To A
B To A
B To C
A To C
A To B
C To B
A To C
B To A
B To C
A To C
A To B
C To B
C To A
B To A
C To B
A To C
A To B
C To B
C To A
B To A
B To C
A To C
B To A
C To B
C To A
B To A
C To B
A To C
A To B
C To B
A To C
B To A
B To C
A To C
A To B
C To B
C To A
B To A
C To B
A To C
A To B
C To B
A To C
B To A
B To C
A To C
B To A
C To B
C To A
B To A
B To C
A To C
A To B
C To B
A To C
B To A
B To C
A To C
B To A
C To B
C To A
B To A
C To B
A To C
A To B
C To B
C To A
B To A
B To C
A To C
B To A
C To B
C To A
B To A
B To C
A To C
A To B
C To B
A To C
B To A
B To C
A To C
A To B
C To B
C To A
B To A
C To B
A To C
A To B
C To B
A To C
B To A
B To C
A To C
B To A
C To B
C To A
B To A
B To C
A To C
A To B
C To B
A To C
B To A
B To C
A To C
A To B
C To B
C To A
B To A
C To B
A To C
A To B
C To B
C To A
B To A
B To C
A To C
B To A
C To B
C To A
B To A
C To B
A To C
A To B
C To B
A To C
B To A
B To C
A To C
A To B
C To B
C To A
B To A
C To B
A To C
A To B
C To B
C To A
B To A
B To C
A To C
B To A
C To B
C To A
B To A
B To C
A To C
A To B
C To B
A To C
B To A
B To C
A To C
B To A
C To B
C To A
B To A
C To B
A To C
A To B
C To B
C To A
B To A
B To C
A To C
B To A
C To B
C To A
B To A
C To B
A To C
A To B
C To B
A To C
B To A
B To C
A To C
A To B
C To B
C To A
B To A
C To B
A To C
A To B
C To B
A To C
B To A
B To C
A To C
B To A
C To B
C To A
B To A
B To C
A To C
A To B
C To B
A To C
B To A
B To C
A To C
A To B
C To B
C To A
B To A
C To B
A To C
A To B
C To B
C To A
B To A
B To C
A To C
B To A
C To B
C To A
B To A
C To B
A To C
A To B
C To B
A To C
B To A
B To C
A To C
A To B
C To B
C To A
B To A
C To B
A To C
A To B
C To B
A To C
B To A
B To C
A To C
B To A
C To B
C To A
B To A
B To C
A To C
A To B
C To B
A To C
B To A
B To C
A To C
B To A
C To B
C To A
B To A
C To B
A To C
A To B
C To B
C To A
B To A
B To C
A To C
B To A
C To B
C To A
B To A
B To C
A To C
A To B
C To B
A To C
B To A
B To C
A To C
A To B
C To B
C To A
B To A
C To B
A To C
A To B
C To B
A To C
B To A
B To C
A To C
B To A
C To B
C To A
B To A
B To C
A To C
A To B
C To B
A To C
B To A
B To C
A To C
B To A
C To B
C To A
B To A
C To B
A To C
A To B
C To B
C To A
B To A
B To C
A To C
B To A
C To B
C To A
B To A
C To B
A To C
A To B
C To B
A To C
B To A
B To C
A To C
A To B
C To B
C To A
B To A
C To B
A To C
A To B
C To B
C To A
B To A
B To C
A To C
B To A
C To B
C To A
B To A
B To C
A To C
A To B
C To B
A To C
B To A
B To C
A To C
B To A
C To B
C To A
B To A
C To B
A To C
A To B
C To B
C To A
B To A
B To C
A To C
B To A
C To B
C To A
B To A
B To C
A To C
A To B
C To B
A To C
B To A
B To C
A To C
A To B
C To B
C To A
B To A
C To B
A To C
A To B
C To B
A To C
B To A
B To C
A To C
B To A
C To B
C To A
B To A
B To C
A To C
A To B
C To B
A To C
B To A
B To C
A To C
A To B
C To B
C To A
B To A
C To B
A To C
A To B
C To B
C To A
B To A
B To C
A To C
B To A
C To B
C To A
B To A
C To B
A To C
A To B
C To B
A To C
B To A
B To C
A To C
A To B
C To B
C To A
B To A
C To B
A To C
A To B
C To B
A To C
B To A
B To C
A To C
B To A
C To B
C To A
B To A
B To C
A To C
A To B
C To B
A To C
B To A
B To C
A To C
B To A
C To B
C To A
B To A
C To B
A To C
A To B
C To B
C To A
B To A
B To C
A To C
B To A
C To B
C To A
B To A
B To C
A To C
A To B
C To B
A To C
B To A
B To C
A To C
A To B
C To B
C To A
B To A
C To B
A To C
A To B
C To B
A To C
B To A
B To C
A To C
B To A
C To B
C To A
B To A
B To C
A To C
A To B
C To B
A To C
B To A
B To C
A To C