Tower of Hanoi

There are three pegs. On the first peg, N disks of different radii are stacked from largest at the bottom to smallest at the top.

Move all disks from the first peg to the third peg under the following rules.

1. Only one disk may be moved at a time.
2. A larger disk must never be placed on top of a smaller disk.

Write a program that prints a minimum-length sequence of moves.

The figure below illustrates the case with 5 disks.

The first line contains N, the number of disks initially stacked on the first peg. (1 <= N <= 100)

Print K, the minimum number of moves, on the first line.

If N is at most 20, print the move sequence from the second line onward. Each of the next K lines contains two integers A and B separated by a space, meaning that the top disk on peg A is moved onto peg B.

If N is greater than 20, the move sequence does not need to be printed.