問題文

以下のような条件を満たすグラフを 1 つ出力してください. (Array とは何なのか…)

• $N$ 頂点 $M$ 辺の有向グラフであり, 辺 $i$ ($1\le i\le M$) は頂点 $d{1}_i$ から $d{2}_i$ へ結ぶ. $d{1}_i<d{2}_i$ を満たす必要がある.
• そのとき, 頂点 $1$ から $N$ に行く方法の通り数（頂点 $1$ を始点、頂点$N$ を終点とするパスの個数）はちょうど $K$ である.
• $1\le N\le 32$ を満たす必要がある. また, $i\ne j$ であれば, $d{1}_i\ne d{1}_j$ と $d{2}_i\ne d{2}_j$ のどちらかは満たしている必要がある.

入力

K

$1$ 行に, $0$ 以上 ${10}^9$ 以下の整数 $K$ が与えられる.

出力

$N$ $M$
$d{1}_1$ $d{2}_1$
$d{1}_2$ $d{2}_2$
...
$d{1}_M$ $d{2}_M$

$1$ 行目に, グラフの頂点数 $N$, 辺数 $M$ を出力すること.
$2$ 行目から $M$ 行にわたって, グラフの辺の情報を出力すること.
最後に改行をすること.

サンプル

2

3 3
1 2
1 3
2 3

3

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

12

9 15
1 2
1 3
2 3
2 4
2 8
3 5
4 6
4 7
5 6
5 7
5 8
6 8
6 9
7 9
8 9