给定一个整数 $K$，请构造一个满足以下条件的无向图：

• 顶点数 $N$ 在 $1$ 到 $100$ 之间（含 $1$ 和 $100$）。
• 边数 $M$ 最多为 $1000$。
• 假设所有边都是可区分的，该图中恰好有 $K$ 棵生成树。换句话说，在从 $M$ 条边中选择若干条边并移除其余边的 $2^M$ 种方式中，恰好有 $K$ 种方式使得剩余的边构成一棵生成树。

输入格式

输入通过标准输入给出，格式如下：

$K$

• $K$ 是一个整数。
• $1 \le K \le 10^9$

输出格式

输出一个满足条件的无向图，格式如下。如果存在多个满足条件的图，你可以输出其中任意一个。

$N \ M$ $U_1 \ V_1$ $\vdots$ $U_M \ V_M$

$U_i, V_i$ ($1 \le i \le M$) 表示第 $i$ 条边连接顶点 $U_i$ 和 $V_i$。

样例

样例输入 1

11

样例输出 1

3 6
1 2
1 3
1 3
2 3
2 3
2 3

样例输入 2

54

样例输出 2

4 10
1 2
2 3
2 3
2 3
3 4
3 4
3 4
4 1
4 1
4 1

说明

在第一个样例中，输出的图由下图表示：

例如，选择以下 2 条边构成了该图的一棵生成树：

• 由边 $1-2$ 和 $1-3$ 组成的生成树有 2 种选择方式。
• 由边 $1-2$ 和 $2-3$ 组成的生成树有 3 种选择方式。
• 由边 $1-3$ 和 $2-3$ 组成的生成树有 6 种选择方式。

因此，总共有 11 棵生成树。 此外，下图所示的图也拥有 11 棵生成树，因此以下输出也被视为正确：

2 11
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2