$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$ について順に以下を実行する：
   • $e_i$ を $F_j$ に追加したとき閉路が生じない最小の正の整数 $j$ を見つけ、$F_j$ に $e_i$ を追加する。ここで $e_i$ を追加するとは、$e_i$ の両端点の番号が $u_i, v_i$ であるとき、$F_j$ に $u_i$ 番頂点と $v_i$ 番頂点を結ぶ辺を追加することを意味する。
3. $F_i$ が 1 つ以上の辺を持つ最大の $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$)

2 行目から $(2N-2)$ 行にわたって、$i$ 行目に 3 つの整数 $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$ 個の辺も木をなす。
• 2 本以上の辺で直接結ばれた頂点対が存在しない。
• $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$ に属する辺を表す。