许多树上的编程竞赛问题都是通过重心分解（centroid decomposition）来解决的：给定一棵树，我们首先找到一个重心——即这样一个顶点，删除它后，剩余各连通块的顶点数均不超过原树顶点数的一半。然后，我们从树中移除找到的重心，并对每个剩余的连通块递归地应用此过程。由于每一层中每个连通块的大小至少减小为原来的一半，因此对于一棵有 $n$ 个顶点的树，最多有 $\log_2(n) + 1$ 层（换句话说，对于任何顶点，在算法执行过程中的任何时刻，包含该顶点的连通块最多有 $\log_2(n) + 1$ 个）。

你注意到另一位参赛者在他们的重心分解中犯了一个错误：他们不是寻找重心，而是在每个阶段寻找树的中心——即一个使到树中其他顶点的最大距离最小化的顶点。更正式地说，如果 $d_{ij}$ 是顶点 $i$ 和 $j$ 之间的距离（树边数），则值 $r = \min_i(\max_j(d_{ij}))$ 被称为树的半径，任何满足 $\max_j(d_{kj}) = r$ 的顶点 $k$ 都被称为树的中心。

事实证明，由于这个错误，分解的层数可能会超过 $\log_2(n) + 1$。为了挑战这个解法，你需要构造一棵顶点数不超过 $n$ 的树，使得这种“中心分解”至少有 $\lfloor \sqrt{n} \rfloor$ 层。更准确地说，必须至少有一个顶点，它在分解过程中的某个时刻属于至少 $\lfloor \sqrt{n} \rfloor$ 个不同的子集。

你可以假设，当某阶段的树有多个中心时，分解过程会选择顶点编号最小的那个作为要从树中移除的中心。

输入格式

输入仅包含一行，为一个整数 $n$，$1 \le n \le 100000$。

输出格式

在输出的第一行，打印一个整数 $m$ ($1 \le m \le n$)，表示你构造的树的顶点数。在接下来的 $m - 1$ 行中描述树的边。每条边应由它连接的两个顶点编号描述。顶点编号从 $1$ 到 $m$。

树中必须至少有一个顶点在“选择树的中心（若有多个则选择编号最小的）、从树中移除该中心、并对所有剩余部分递归应用此过程”的过程中，属于至少 $\lfloor \sqrt{n} \rfloor$ 个不同的部分。

样例

样例输入 1

4

样例输出 1

3
1 2
2 3