Hanoi Tower
题号：NC235371
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

有  只猫，从  编号，有三个格子：，编号为奇数的猫从小到大由上到下叠在  上，编号为偶数的猫从小到大由上到下叠在  上。

小猫们按照如下规则移动：

  • 只有三个格子中最上面的猫可以移动，但只能移动到最顶端的猫编号比自己编号大的格子顶端，或者移动到空的格子上。

小猫迅速地按最优策略移动，按从小到大由上到下的顺序叠在了格子  上，由于速度非常的快，因此小 Z 并没有看清楚小猫们是怎么移动的，但他又十分好奇小猫是如何移动的，于是就来向你求助，请你帮帮他吧。

输入描述:

第一行一个数 。

输出描述:

第一行输出一个数  表示最少需要的移动步数。
若 ，则接下来还需要输出移动的方案：
方案每步输出一行，按照 <需要移动的猫的编号> <需要移动到的目标格> 的格式输出。例如 3 A 则表示将  号猫移动至格子 A。
示例1

输入

复制 
3

输出

复制 
5
1 C
3 B
1 A
2 B
1 B

说明

初始状态：
1
3   2
A B C
第一次移动后：
    1
3   2
A B C
第二次移动后：
    1
  3 2
A B C
第三次移动后：
1 3 2
A B C
第四次移动后：
  2 
1 3
A B C
第五次移动后：
  1
  2
  3
A B C