對於由 $1$ 到 $N$ 的 $N$ 個頂點和 $M$ 條邊組成的加權無向簡單圖 $G$，將森林分數定義如下：

1. 令 $F_1, F_2, F_3, \ldots, F_M$ 分別為由 $1$ 到 $N$ 的 $N$ 個頂點組成且沒有邊的圖。
2. 將 $G$ 的邊按權重升序排列為 $e_1, e_2, \ldots, e_M$，依序對 $i = 1, 2, \ldots, M$ 執行以下步驟：
   • 找出最小的正整數 $j$，使得將 $e_i$ 加入 $F_j$ 後不會產生環，然後將 $e_i$ 加入 $F_j$。這裡加入 $e_i$ 的意思是：若 $e_i$ 的兩個端點編號為 $u_i$ 和 $v_i$，則在 $F_j$ 中加入連接 $u_i$ 和 $v_i$ 的邊。
3. 令 $i$ 為使得 $F_i$ 至少含有一條邊的最大值，稱此 $i$ 為圖 $G$ 的森林分數。

你接到的任務是：對於給定的正整數 $k$，生成一個森林分數恰好為 $k$、且頂點數不超過 $2024$ 的圖 $G$。

這個問題對你來說太簡單了，因此你發現尋找滿足以下額外條件的 $G$ 更有趣：

• 若 $G$ 的頂點數為 $N$，則邊數為 $(2N-2)$。
• 可以將 $G$ 的 $(N-1)$ 條邊塗成紅色，另外 $(N-1)$ 條邊塗成藍色，使得只保留紅色邊時形成一棵樹，只保留藍色邊時也形成一棵樹。

給定 $k$，請找出滿足條件的 $G$ 並輸出。

輸入格式

第一行給定一個整數 $k$。（$2 \le k \le 12$）

輸出格式

第一行輸出圖 $G$ 的頂點數 $N$。（$2 \le N \le 2024$）

接下來 $(2N-2)$ 行，第 $i$ 行輸出三個整數 $a_i, b_i, c_i$，以空格分隔。（$1 \le a_i, b_i \le N$；$a_i \neq b_i$；$1 \le c_i \le 10^9$）這表示存在一條連接頂點 $a_i$ 和 $b_i$、權重為 $c_i$ 的邊。

$G$ 必須滿足以下條件：

• 所有邊的權重均相異，即 $c_i$ 之間互不相同。
• 輸出的前 $N-1$ 條邊構成一棵樹。同樣地，其後的 $N-1$ 條邊也構成一棵樹。
• 不存在由兩條或以上邊直接連接的頂點對。
• $G$ 的森林分數為 $k$。

範例

輸入 1

3

輸出 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

說明

以下是 $k=3$ 時正確答案的範例。

如上圖所示，該圖由兩個不相交的樹組成。

計算森林分數可得 $3$。紅色邊屬於 $F_1$，藍色邊屬於 $F_2$，綠色邊屬於 $F_3$。