Utilizando únicamente resistores con resistencia $1\ [\Omega]$, construya un resistor con resistencia $\sqrt{D}\ [\Omega]$.

Se le proporciona un entero positivo $D$. Construya un grafo conexo no dirigido que satisfaga todas las siguientes condiciones. Bajo las restricciones de este problema, se puede demostrar que tal grafo siempre existe.

• El número de vértices $N$ está entre 2 y 300, inclusive, y cada vértice tiene una etiqueta distinta del 1 al $N$.
• El número de aristas $M$ es como máximo 300, y se permiten bucles y aristas múltiples.
• La "resistencia efectiva del vértice 1 al vértice $N$", definida a continuación, se encuentra dentro de un error absoluto de $\pm 10^{-6}$ respecto a $\sqrt{D}$.

Sea $G$ un grafo conexo no dirigido con $n$ vértices y $m$ aristas ($n \ge 2$), y suponga que la $j$-ésima arista conecta los vértices $a_j, b_j$. Considere asignar un número real $V_i$ ($i = 1, 2, \dots, n$) a cada vértice del grafo $G$, y un número real $I_j$ ($j = 1, 2, \dots, m$) a cada arista, de modo que se satisfagan todas las siguientes ecuaciones:

• $I_j = V_{a_j} - V_{b_j}$ ($j = 1, 2, \dots, m$)
• $\sum_{b_j=i} I_j - \sum_{a_j=i} I_j = 0$ ($i = 2, 3, \dots, n - 1$)
• $\sum_{b_j=n} I_j - \sum_{a_j=n} I_j = 1$

Se puede demostrar que tal asignación siempre existe y, además, que el valor de $V_1 - V_n$ está determinado de forma única. Definimos este valor como la "resistencia efectiva del vértice 1 al vértice $n$".

Entrada

La entrada consiste en un único entero positivo $D$ ($1 \le D \le 5000$).

Salida

En la primera línea, imprima el número de vértices $N$ y el número de aristas $M$ del grafo construido, en este orden, separados por espacios.

En cada una de las siguientes $M$ líneas, la $i$-ésima línea ($i = 1, 2, \dots, M$) debe contener los extremos de la $i$-ésima arista elegida, separados por un espacio.

Si existen múltiples grafos que satisfacen las condiciones, se puede imprimir cualquiera de ellos.

Ejemplos

Entrada 1

1

Salida 1

4 5
1 2
1 3
2 3
2 4
3 4

Nota

La siguiente es una ilustración de la salida para el primer ejemplo.

Que la resistencia efectiva del vértice 1 al vértice $n$ sea $1\ [\Omega]$ se puede explicar de la siguiente manera:

• Dado que todos los resistores tienen una resistencia de $1\ [\Omega]$, y por simetría los potenciales en los vértices 2 y 3 son iguales, el resistor entre ellos puede tratarse como si no existiera.
• Como resultado, el circuito se reduce a dos ramas en paralelo, cada una consistente en dos resistores de $1\ [\Omega]$ en serie.
• La resistencia efectiva de dos resistores de $1\ [\Omega]$ en serie es $2\ [\Omega]$, y la resistencia efectiva de dos resistores de $2\ [\Omega]$ en paralelo es $1\ [\Omega]$.

La siguiente salida también se considera correcta:

2 1
1 2