El juego de la Torre de Hanói consta de tres pilas (izquierda, central y derecha) y ~n~ discos redondos de diferentes tamaños. Inicialmente, la pila izquierda contiene todos los discos, en orden creciente de tamaño de arriba a abajo. El objetivo es mover todos los discos a la pila derecha usando la pila central. En cada movimiento, se puede mover el disco superior de una pila a otra. Además, no se permite colocar un disco más grande sobre uno más pequeño.

La tarea es encontrar una solución que minimice el número de movimientos.

Entrada

La única línea de entrada tiene un entero ~n~: el número de discos.

Salida

Primero, imprime un entero ~k~: el número mínimo de movimientos. Después, imprime ~k~ líneas que describen los movimientos. Cada línea tiene dos enteros ~a~ y ~b~: se mueve un disco de la pila ~a~ a la pila ~b~.

Restricciones

• ~1 \leq n \leq 16~

Ejemplo de Entrada

2

Ejemplo de Salida

3
1 2
1 3
2 3