抵抗値 $1 \, [\Omega]$ の抵抗器のみを用いて、抵抗値 $\sqrt{D} \, [\Omega]$ の抵抗器を構成せよ。

正の整数 $D$ が与えられる。以下のすべての条件を満たす連結な無向グラフを1つ構成せよ。この問題の制約下において、そのようなグラフは常に存在することが証明できる。

• 頂点数 $N$ は $2$ 以上 $300$ 以下であり、各頂点には $1$ から $N$ までの異なるラベルが付いている。
• 辺の数 $M$ は $300$ 以下であり、自己ループや多重辺も許容される。
• 以下で定義される「頂点 $1$ から頂点 $N$ への合成抵抗」は、$\sqrt{D}$ との絶対誤差が $\pm 10^{-6}$ 以内であること。

$G$ を $n$ 個の頂点と $m$ 個の辺を持つ連結な無向グラフ（$n \ge 2$）とし、$j$ 番目の辺が頂点 $a_j, b_j$ を結んでいるとする。グラフ $G$ の各頂点に実数 $V_i$ ($i = 1, 2, \dots, n$) を、各辺に実数 $I_j$ ($j = 1, 2, \dots, m$) を割り当て、以下のすべての方程式が満たされるようにする。

• $I_j = V_{a_j} - V_{b_j} \quad (j = 1, 2, \dots, m)$
• $\sum_{b_j=i} I_j - \sum_{a_j=i} I_j = 0 \quad (i = 2, 3, \dots, n - 1)$
• $\sum_{b_j=n} I_j - \sum_{a_j=n} I_j = 1$

このような割り当ては常に存在し、さらに $V_1 - V_n$ の値は一意に定まることが証明できる。この値を「頂点 $1$ から頂点 $n$ への合成抵抗」と定義する。

入力

入力は単一の正の整数 $D$ からなる。($1 \le D \le 5000$)

出力

1行目に、構成したグラフの頂点数 $N$ と辺の数 $M$ をこの順に空白区切りで出力せよ。

続く $M$ 行の各行には、$i$ 番目の辺 ($i = 1, 2, \dots, M$) の両端の頂点を空白区切りで出力せよ。

条件を満たすグラフが複数存在する場合、そのうちのどれを出力してもよい。

入出力例

入力 1

1

出力 1

4 5
1 2
1 3
2 3
2 4
3 4

注記

以下は、最初の入出力例に対する出力の図である。

頂点 $1$ から頂点 $n$ への合成抵抗が $1 \, [\Omega]$ であることは、以下のように説明できる。

• すべての抵抗器の抵抗値は $1 \, [\Omega]$ であり、対称性により頂点 $2$ と頂点 $3$ の電位は等しいため、それらの間の抵抗器は存在しないものとして扱うことができる。
• その結果、回路は2つの並列な枝に簡約され、各枝は $1 \, [\Omega]$ の抵抗器2つが直列に接続されたものとなる。
• $1 \, [\Omega]$ の抵抗器2つを直列に接続した合成抵抗は $2 \, [\Omega]$ であり、$2 \, [\Omega]$ の抵抗器2つを並列に接続した合成抵抗は $1 \, [\Omega]$ となる。

以下の出力も正解とみなされる。

2 1
1 2