問題文

頂点に $1$ から $N$ までの番号がついた $N$ 頂点の単純無向グラフであって、その次数列の要素の種類数が最大となるようなものを $1$ つ構成してください。

備考

• ある無向グラフ $G$ が 単純 であるとは、$G$ が自己ループや多重辺を持たないことを指します。
• ある無向グラフ $G$ の 次数列 とは、$G$ の各頂点の次数を降順に並べた数列を指します。

入力

$N$

• $N$ は $2 \leq N \leq 500$ を満たす整数

出力

以下のフォーマットで、構成したグラフを出力してください。出力はすべて整数でなければなりません。

$M$
$u_1\ v_1$
$u_2\ v_2$
$\vdots$
$u_M\ v_M$

出力の $i+1\ (1 \leq i \leq M)$ 行目は、$i$ 番目の辺において、頂点 $u_i$ と $v_i$ が双方向に結ばれていることを表します。ただし、$1 \leq u_i,v_i \leq N$ を満たす必要があります。

辺は任意の順番で出力して構いません。

最後に改行してください。

サンプル

3

2
1 3
2 3