e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more
Problems

Towers of Hanoi

Towers of Hanoi

Three pegs are given. The first peg contains some disks in ascending order of their size from top to bottom. The other two pegs are empty. You must move all disks from the first peg to the second. You can move each time only one disk. It is not allowed to put a larger disk on a smaller one.

Input

The number of disks n (1n19) on the first peg.

Output

In each line print two numbers – the peg numbers from which and where the disk is moved. The solution must be the shortest.

Time limit 5 seconds
Memory limit 244.24 MiB
Input example #1
3
Output example #1
1 2
1 3
2 3
1 2
3 1
3 2
1 2