Tower of Hanoi

Medium#recursion· solved by 0 · time limit 2.0 s

Move $n$ discs from rod A to rod C using rod B, never placing a bigger disc on a smaller one. Print the minimum number of moves, then each move as from to, using the standard recursive solution.

Input

A single integer $n$ .

Output

The number of moves, then one move per line.

Constraints

$1 \le n \le 10$

Sample 1

Input

Output

3
A B
A C
B C