Towers of Hanoi Puzzle

Solve the classic Towers of Hanoi puzzle. You are given an integer N representing the number of disks. The disks are initially stacked on rod A in decreasing order of size (largest at the bottom). The goal is to move the entire stack to rod C, using rod B as an auxiliary.

Only one disk can be moved at a time, and a larger disk must never be placed on top of a smaller disk. The minimum number of moves required to solve the puzzle is given by the formula: \(2^N - 1\).

Your task is to print the sequence of moves to solve the puzzle with the following format for each move:

Move disk X from rod Y to rod Z

Use the rod labels as follows: source: A, destination: C, and auxiliary: B.

inputFormat

The input consists of a single integer N (1 ≤ N ≤ 20) provided via standard input. This integer represents the number of disks.

The rods are predefined as follows: source rod is A, destination rod is C, and auxiliary rod is B.

outputFormat

Print the sequence of moves, one per line, required to solve the Towers of Hanoi puzzle. Each line must follow the format:

Move disk X from rod Y to rod Z

where X is the disk number, and Y and Z are the rod labels.

## sample

1

Move disk 1 from rod A to rod C