In this problem you will be required to provide the best solution to the Tower of Hanoi.

Tower of Hanoi is a mathematical game that contains three rods, a more detailed video description can be found here.

You are task is, given the number of disks on Rod 1, give each step to move all disks to Rod 3 most efficiently (smallest number of steps). Just a hint, the solution is unique.

Input Specification

The first line will contain a single integer \(N\), indicating the number of disks on Rod 1. (\(1 < N < 20\))

Output Specification

The output should contain the steps to move all disks to rod 3. Each line will contain 2 integers \(i\) and \(j\). Line \(m\)'s number \(i_m\) and \(j_m\) means in step \(m\), you move the disk on top of rod \(i\) to rod \(j\).

Sample Input 1

3

Sample Output 1

1 3
1 2
3 2
1 3
2 1
2 3
1 3

Explaination of Sample Output

Initial:

Rod 1: 1 2 3
Rod 2: _
Rod 3: _

Step 1: 1 3, move disk 1 from rod 1 to rod 3. The disks on 3 rods now

Rod 1: 2 3
Rod 2: _
Rod 3: 1

Step 2: 1 2, move disk 2 from rod 1 to rod 3. The disks on 3 rods now

Rod 1: 3
Rod 2: 2
Rod 3: 1

Step 3: 3 2, move disk 1 from rod 3 to rod 2. The disks on 3 rods now

Rod 1: 3
Rod 2: 1 2
Rod 3: _

Step 4: 1 3, move disk 3 from rod 1 to rod 3. The disks on 3 rods now

Rod 1: _
Rod 2: 1 2
Rod 3: 3

Step 5: 2 1, move disk 1 from rod 2 to rod 1. The disks on 3 rods now

Rod 1: 1
Rod 2: 2
Rod 3: 3

Step 6: 2 3, move disk 2 from rod 2 to rod 3. The disks on 3 rods now

Rod 1: 1
Rod 2: _
Rod 3: 2 3

Step 7: 1 3, move disk 1 from rod 2 to rod 1. The disks on 3 rods now

Rod 1: _
Rod 2: _
Rod 3: 1 2 3

Sample Input 2 (refer to the video)

4

Sample Output 2

1 2
1 3
2 3
1 2
3 1
3 2
1 2
1 3
2 3
2 1
3 1
2 3
1 2
1 3
2 3