我们有一个大小为 $n$ 的完全无向图：对于所有满足 $1 \le u < v \le n$ 的顶点对 $(u, v)$，在 $u$ 和 $v$ 之间都存在一条边。请找到一种方法，将该图的边集表示为若干棵 $n$ 个顶点的树的并集。

设 $k$ 为树的数量，$T_1, \ldots, T_k$ 为这些树。则：

• 每棵树 $T_i$ 都应该是一棵包含 $n$ 个顶点（编号从 $1$ 到 $n$）和 $n - 1$ 条边的树。
• 所有树的所有边的并集应该构成该完全图。
• 树的数量 $k$ 应该尽可能小。

输入格式

第一行包含一个整数 $n$，表示图的大小（$2 \le n \le 1000$）。

输出格式

第一行输出树的数量 $k$。 数量 $k$ 应该尽可能小。 接下来，依次输出这 $k$ 棵树，中间不要有空行。

对于每棵树，输出 $n - 1$ 行，表示它的边。 对于每条边，输出一行，包含两个整数 $u$ 和 $v$，表示被这条边连接的顶点。

如果存在多个最优解，输出其中任意一个即可。

样例

样例输入 1

2

样例输出 1

1
1 2

样例输入 2

3

样例输出 2

2
1 2
1 3
1 3
2 3