考虑一个包含 $n \ge 2$ 个顶点的图，图中没有自环或重边。每条边可以被染成 $k$ 种颜色中的一种。如果每种颜色的边都构成该图的一棵生成树（即对于每种颜色 $c$，任意两个顶点之间都存在唯一的仅使用颜色 $c$ 的边的路径），我们称这种染色是“合法的”（proper）。记颜色 $c$ 的生成树为 $T_c$。

如果对于任意两种颜色 $c$ 和 $d$，以及任意两个不同的顶点 $u$ 和 $v$，以下命题成立，我们称这种合法的染色是“安全的”（safe）： $\text{path}_{T_c}(u, v) \cap \text{path}_{T_d}(u, v) = \{u, v\}$，其中 $\text{path}_T(u, v)$ 是树 $T$ 中位于 $u$ 和 $v$ 之间简单路径上的所有顶点的集合（包含 $u$ 和 $v$ 本身）。

你的任务是构造这样一个图，其边被染成 $k$ 种颜色，并构成一个安全的合法染色。

输入格式

输入的第一行也是唯一一行包含一个正整数 $k$ ($2 \le k \le 100$)，表示你应该在图中使用的颜色数量。

输出格式

第一行输出 $n \ge 2$：图中顶点的数量。

然后，输出 $k$ 组边，每组包含 $n - 1$ 条边，分别代表每种颜色的边。每条边输出为一行两个整数 $a_i, b_i$ ($1 \le a_i, b_i \le n, a_i \neq b_i$)。

你的输出必须满足条件 $(n - 1) \cdot k \le 10^6$。图中不得有重边。

你可以输出任何合法的答案。题目保证至少存在一个解。

样例

输入 1

2

输出 1

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