给定一个正整数 $K \le 60$。请构造一个顶点数不超过 20 的图，使其满足以下性质：图中恰好有 $K$ 对无序顶点对 $(u, v)$，使得在图中存在一条连接 $u$ 和 $v$ 的哈密顿路径。

可以证明，在这些约束条件下，解总是存在的。

回想一下，哈密顿路径是指图中经过每个顶点恰好一次的路径。

输入格式

输入仅包含一行，为一个整数 $K$ ($1 \le K \le 60$)。

输出格式

第一行输出两个整数 $n$ 和 $m$ ($2 \le n \le 20, 0 \le m \le \frac{n(n-1)}{2}$)，分别表示图中顶点的数量和边的数量。

接下来的 $m$ 行，每行输出两个整数 $u$ 和 $v$ ($1 \le u, v \le n, u \neq v$)，表示图中的一条边 $(u, v)$。所有边必须互不相同。

样例

样例输入 1

1

样例输出 1

2 1
1 2

样例输入 2

4

样例输出 2

4 4
1 2
1 3
2 3
3 4

样例输入 3

3

样例输出 3

3 3
1 2
2 3
3 1