Para una gráfica simple no dirigida con pesos $G$ que consta de $N$ vértices numerados del $1$ al $N$ y $M$ aristas, la puntuación de bosque se define de la siguiente manera:

1. Sean $F_1$, $F_2$, $F_3$, $\ldots$, $F_M$ cada una gráficas sin aristas con $N$ vértices numerados del $1$ al $N$.
2. Sean las aristas de $G$ ordenadas por peso creciente $e_1$, $e_2$, $\ldots$, $e_M$. Para $i=1,2,\ldots,M$, se realiza lo siguiente en orden:
   • Encuentre el menor entero positivo $j$ tal que al agregar $e_i$ a $F_j$ no se forme un ciclo, y agregue $e_i$ a $F_j$. Aquí, agregar $e_i$ significa agregar una arista que conecta los vértices $u_i$ y $v_i$ (los extremos de $e_i$) a $F_j$.
3. El mayor $i$ para el cual $F_i$ tiene al menos una arista se denomina la puntuación de bosque de la gráfica $G$.

Se te ha encomendado generar una gráfica $G$ con a lo sumo $2024$ vértices y tal que su puntuación de bosque sea exactamente $k$, para un entero positivo $k$.

Dado que este problema te resultó demasiado fácil, te pareció más interesante encontrar una $G$ que además satisfaga las siguientes condiciones:

• Si $N$ es el número de vértices de $G$, entonces el número de aristas es $(2N-2)$.
• Entre las aristas de $G$, se pueden colorear $(N-1)$ de rojo y las otras $(N-1)$ de azul, de modo que si se conservan solo las aristas rojas se forma un árbol, y si se conservan solo las aristas azules también se forma un árbol.

Dado $k$, encuentra e imprime una gráfica $G$ que cumpla las condiciones.

Entrada

La primera línea contiene un entero $k$. ($2 \le k \le 12$)

Salida

La primera línea debe contener el número de vértices $N$ de la gráfica $G$. ($2 \le N \le 2024$)

A partir de la segunda línea, se deben imprimir $(2N-2)$ líneas. La $i$-ésima línea debe contener tres enteros $a_i$, $b_i$, $c_i$ separados por espacios. ($1 \le a_i, b_i \le N$; $a_i \neq b_i$; $1 \le c_i \le 10^9$) Esto indica que existe una arista de peso $c_i$ que conecta los vértices $a_i$ y $b_i$.

$G$ debe cumplir las siguientes condiciones:

• Todos los pesos de las aristas son distintos. Es decir, los $c_i$ son todos diferentes.
• Las primeras $N-1$ aristas impresas forman un árbol. De igual manera, las siguientes $N-1$ aristas impresas también forman un árbol.
• No existe un par de vértices conectados directamente por más de una arista.
• La puntuación de bosque de $G$ es $k$.

Ejemplos

Entrada 1

3

Salida 1

5
1 2 8
2 3 1
3 4 2
4 5 5
1 3 6
3 5 4
5 2 7
2 4 3

Nota

A continuación se muestra un ejemplo de una respuesta correcta para $k=3$.

La gráfica anterior está compuesta por dos árboles que no se superponen, como se puede observar en la siguiente figura.

Al calcular la puntuación de bosque, se obtiene $3$ como se muestra a continuación. Las aristas rojas pertenecen a $F_1$, las azules a $F_2$ y las verdes a $F_3$.