Problem Statement

You are given a positive integer $N$. Construct one weighted connected undirected graph with $N$ vertices and $M$ edges that satisfies the following conditions. Here, the vertices are numbered from $1$ to $N$, and the edges are numbered from $1$ to $M$.

• The graph contains no self-loops (multiple edges are allowed).
• $M \leq 2N-3$
• For every pair of integers $(i,j)$ satisfying $1 \leq i < j \leq N$, there exists a simple path from vertex $i$ to vertex $j$ such that the sum of the weights of the edges on the path is a perfect square.
• The weights of all edges are pairwise distinct integers between $1$ and $200$, inclusive.

Furthermore, in the graph you construct, let $P_{i,j}$ be one simple path from vertex $i$ to vertex $j$ such that the sum of the weights of the edges on the path is a perfect square. Also, let $Q_{i,j}$ be the sequence of the numbers of the edges that $P_{i,j}$ passes through, arranged in the order they are traversed. Output $Q_{i,j}$ for every pair of integers $(i,j)$ satisfying $1 \leq i < j \leq N$.

It can be shown that a graph satisfying the conditions can always be constructed under the given constraints.

Constraints

• $2 \leq N \leq 100$
• All input values are integers.

Input

The input is given from Standard Input in the following format.

$N$

Output

First, output a graph satisfying the conditions. On the first line, output the number of edges $M$. On the $i$-th of the following $M$ lines, output the endpoints $U_{i}$, $V_{i}$ and the weight $C_{i}$ of edge $i$ in the following format.

$U_{i}$ $V_{i}$ $C_{i}$

Then, for every pair of integers $(i,j)$ satisfying $1 \leq i < j \leq N$, in lexicographical order of $(i,j)$, output in the following format.

$|Q_{i,j}|$  $Q_{i,j}$

Here, separate the elements of $Q_{i,j}$ with spaces.

Sample

3

3
1 2 16
2 3 9
1 3 25
1 1
1 3
1 2