说明

时间限制：1 Sec 内存限制：256 MB 输入文件：path.in 输出文件：path.out

请输出一个满足以下全部条件的有向图。

- 这是一个 $N$ 个顶点、$M$ 条边的有向图。第 $i$ 条边连接顶点 $d1_i$ 指向 $d2_i$，必须满足 $d1_i \lt d2_i$。

- 从顶点 $1$ 走到顶点 $N$ 的路径总数（以顶点 $1$ 为起点、顶点 $N$ 为终点的路径条数）恰好等于 $K$。

- 需要满足 $1 \leq N \leq 32$。另外，对于任意 $i \neq j$，必须满足 $d1_i \neq d1_j$ 和 $d2_i \neq d2_j$ 至少其中一条成立。

本题为特殊判题，存在多组合法答案，输出任意一组均可。

输入格式

一行一个整数 $K$。

输出格式

第一行两个整数 $N,M$，分别代表顶点数、边数。

接下来 $M$ 行，每行两个整数 $d1_i,d2_i$，描述一条边。

样例

样例 1

2

3 3
1 2
1 3
2 3

样例说明：

存在 $1 \to 3$、$1 \to 2 \to 3$，一共 $2$ 条路径。

样例 2

3

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

样例 3

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

数据范围

对于 15% 的数据，$K \le 20$。

对于 40% 的数据，$K \le 200$。

对于 50% 的数据，$K \le 2000$。

对于 100% 的数据，$0 \le K \le 10^9$。