You are given $$$N$$$ discs of different sizes, stacked from largest at the bottom to smallest at the top on rod $$$1$$$. There are two other rods, $$$2$$$ and $$$3$$$, which are empty.

Your task is to move all the discs from rod $$$1$$$ to rod $$$3$$$, obeying the following rules in the minimum number of moves:

• Only one disc may be moved at a time.
• Each move consists of taking the upper disc from one of the rods and placing it on top of another rod.
• A disc may not be placed on top of a smaller disc.

A single integer: $$$ N\;(1 \le N \le 21) $$$

On the first line, print an integer $$$M$$$ —the total number of moves.

Then print exactly $$$M$$$ lines, each containing two space-separated integers: $$$ S\;T $$$ indicating that the top disc is moved from rod $$$S$$$ to rod $$$T$$$.