Tower of Hanoi Problem

The Tower of Hanoi is a classic mathematical puzzle which involves moving a set of disks from one rod to another. You are given three rods and n disks of different sizes which can slide onto any rod. The puzzle starts with the disks neatly stacked in ascending order of size on one rod, the smallest at the top, thus making a conical shape.

The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:

1. Only one disk can be moved at a time.
2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty rod.
3. No disk may be placed on top of a smaller disk.

In mathematical terms, if you denote the number of disks by $n$, the minimum number of moves required is $2^n - 1$. Your task is to implement a solution for this puzzle using recursion.

inputFormat

The input is provided via standard input (stdin) and consists of a single integer $n$ $(1 \le n \le 20)$ representing the number of disks.

outputFormat

Output to standard output (stdout) a series of moves, one per line. Each move should be represented by two integers separated by a single space, indicating the source rod and the destination rod respectively.## sample

1

1 3