For a weighted undirected simple graph $G$ consisting of $N$ vertices numbered $1$ through $N$ and $M$ edges, the forest score is defined as follows:

1. Let $F_1, F_2, F_3, \ldots, F_M$ each be a graph with $N$ vertices numbered $1$ through $N$ and no edges.
2. Let $e_1, e_2, \ldots, e_M$ be the edges of $G$ sorted in non‑decreasing order of weight. For $i = 1, 2, \ldots, M$, perform the following step in order:
   • Find the smallest positive integer $j$ such that adding $e_i$ to $F_j$ does not create a cycle, and add $e_i$ to $F_j$. Adding $e_i$ means that if the two endpoints of $e_i$ are $u_i$ and $v_i$, then an edge connecting vertex $u_i$ and vertex $v_i$ is added to $F_j$.
3. The forest score of graph $G$ is the largest $i$ such that $F_i$ contains at least one edge.

You are tasked with constructing a graph $G$ whose forest score is exactly $k$ and which has at most $2024$ vertices.

Since this problem was too easy for you, you find it more interesting to look for a $G$ that also satisfies the following additional conditions:

• Let $N$ be the number of vertices of $G$. Then the number of edges is $(2N-2)$.
• It is possible to color $(N-1)$ of the edges red and the other $(N-1)$ edges blue so that, if only the red edges are kept, they form a tree, and if only the blue edges are kept, they also form a tree.

Given $k$, find and output a $G$ that satisfies the conditions.

Input

The first line contains an integer $k$. ($2 \le k \le 12$)

Output

The first line contains the number $N$ of vertices of graph $G$. ($2 \le N \le 2024$)

The next $(2N-2)$ lines each contain three integers $a_i$, $b_i$, $c_i$ separated by spaces. ($1 \le a_i, b_i \le N$; $a_i \neq b_i$; $1 \le c_i \le 10^9$) This means there is an edge of weight $c_i$ connecting vertex $a_i$ and vertex $b_i$.

$G$ must satisfy the following conditions:

• All edge weights are distinct. That is, all $c_i$ are pairwise different.
• The first $N-1$ edges you output form a tree. Similarly, the next $N-1$ edges also form a tree.
• No pair of vertices is directly connected by more than one edge.
• The forest score of $G$ is $k$.

Examples

Input 1

3

Output 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

Note

Below is an example of a correct answer for $k=3$.

The graph above consists of two disjoint trees, as can be seen in the figure below.

Calculating the forest score gives $3$ as shown below. The red edges belong to $F_1$, the blue edges to $F_2$, and the green edges to $F_3$.