Descripción

El juego de la Torre de Hanói consiste en tres pilas (izquierda, central y derecha) y n discos redondos de diferentes tamaños. Inicialmente, la pila de la izquierda tiene todos los discos, en orden creciente de tamaño de arriba hacia abajo.

El objetivo es mover todos los discos a la pila de la derecha utilizando la pila central como auxiliar. En cada movimiento puedes mover el disco superior de una pila a otra. Además, no está permitido colocar un disco más grande sobre uno más pequeño.

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

Entrada

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

Salida

Primero imprime un entero k: el número mínimo de movimientos.

Después de esto, imprime k líneas que describen los movimientos.
Cada línea contiene dos enteros a y b: se mueve un disco de la pila a a la pila b.

Restricciones

\(1 \leq n \leq 16 \)

Ejemplo

Entrada

2

Salida

3
1 2
1 3
2 3