Tower of Hanoi Puzzle

Solve the classic Tower of Hanoi problem. Given an integer n representing the number of disks, you are required to move all disks from the source rod (A) to the destination rod (C) using an auxiliary rod (B). Only one disk can be moved at a time, and a larger disk cannot be placed on top of a smaller disk.

The minimum number of moves required is given by the formula: \(2^n - 1\).

Your task is to output the total number of moves followed by a list of moves. Each move is represented by a pair of uppercase letters indicating the source rod and the destination rod.

inputFormat

The input consists of a single integer \(n\) (1 \(\leq\) n \(\leq\) 15) that represents the number of disks.

outputFormat

The first line of the output should contain the minimum number of moves required to solve the puzzle. Each subsequent line should display a move in the format "X Y", where X is the source rod and Y is the destination rod.

## sample

1

1
A C

</p>