Vera 热爱徒步，她打算建立自己的步道网络。该网络由 $V$ 个编号为 $1$ 到 $V$ 的地点以及 $E$ 条双向步道组成，其中第 $i$ 条步道直接连接两个不同的地点 $a_i$ 和 $b_i$。Vera 希望她的网络是连通的，即任意两个地点之间都可以通过步道相互到达。同一个地点对之间可能存在多条直接相连的步道。

Vera 认为，如果两个地点 $a, b$（满足 $a < b$）之间可以通过步道从 $a$ 走到 $b$ 再回到 $a$，且过程中不经过任何一条重复的步道，则称这两个地点构成一个“优美连通对”。她认为如果她的步道网络恰好有 $K$ 个优美连通对，那么这个网络就是优美的。

Vera 不希望她的网络规模过大，因此网络应满足 $1 \le V, E \le 5000$。给定 $K$，请帮助 Vera 找到任意一个优美的步道网络。

输入格式

输入仅一行，包含一个整数 $K$ ($0 < K \le 10^7$)。

对于 25 分中的 3 分，满足 $K \le 1000$。 对于另外 25 分中的 6 分，满足 $K \le 10^5$。

输出格式

按以下格式输出一个优美的网络：

• 第一行包含顶点数 $V$，后跟一个空格，再跟边数 $E$；
• 接下来的 $E$ 行，每行包含两个整数 $a_i$ 和 $b_i$，中间用空格隔开，表示地点 $a_i$ 和 $b_i$ 之间的一条步道 ($1 \le i \le E$)。

步道可以按任意顺序输出。每条步道的两个地点也可以按任意顺序输出。如果存在多个优美的步道网络，输出其中任意一个即可。题目保证一定存在解。

样例

样例输入 1

2

样例输出 1

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

说明 1

两个优美连通对分别是 $1, 2$ 和 $3, 4$。

样例输入 2

6

样例输出 2

4 4
1 2
2 3
3 4
4 1

说明 2

所有的地点对都构成了优美连通对。