Towers of Hanoi

The Towers of Hanoi is a classic puzzle that involves moving a set of disks from one rod to another, following these rules:

• Only one disk can be moved at a time.
• A disk can only be placed on top of a larger disk or on an empty rod.
• All disks start on the source rod in decreasing size (largest at the bottom).

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

For this problem, you will be given a single integer \(n\) representing the number of disks. The initial configuration is always with the source rod as 1, the target rod as 3, and the auxiliary rod as 2. Your task is to print the sequence of moves to solve the puzzle.

inputFormat

The input consists of a single integer \(n\) (\(1 \leq n \leq 20\)), which represents the number of disks.

outputFormat

Print the sequence of moves required to solve the Towers of Hanoi puzzle. Each move is printed on a new line in the format: "source target", where source and target are the rod numbers. The moves should follow the optimal solution which uses \(2^n - 1\) moves.

## sample

1

1 3

</p>