给你一个整数$$$n$$$。
您应该找到满足以下条件的对 $$$(x_1, y_1)$$$, $$$(x_2, y_2)$$$, ..., $$$(x_q, y_q)$$$ ($$$1 \leq x_i, y_i \leq n$$$) 的列表。
让我们考虑一些函数 $$$f: \mathbb{N} \times \mathbb{N} \to \mathbb{N}$$$ (我们将 $$$\mathbb{N}$$$ 定义为正整数集合)。换句话说,$$$f$$$ 是一个为一对正整数返回正整数的函数。
让我们创建一个数组 $$$a_1, a_2, \ldots, a_n$$$,其中最初 $$$a_i = i$$$。
您将执行 $$$q$$$ 操作,在其中 $$$i$$$ 中您将:
1. 赋值 $$$t = f(a_{x_i}, a_{y_i})$$$ ($$$t$$$ 是临时变量,仅用于接下来的两次赋值);
2. 赋值 $$$a_{x_i} = t$$$;
3. 赋值 $$$a_{y_i} = t$$$。
也就是说,您需要同时将 $$$a_{x_i}$$$ 和 $$$a_{y_i}$$$ 更改为 $$$f(a_{x_i}, a_{y_i})$$$。请注意,在此过程中,对于一对固定的 $$$p$$$ 和 $$$q$$$ 来说,$$$f(p, q)$$$ 始终相同。
最后,数组$$$a$$$中最多应该有两个不同的数字。
对于任何函数 $$$f$$$ 都应该如此。
找到任何可能的配对列表。对的数量不应超过 $$$5 \cdot 10^5$$$。
输入
单行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 15\,000$$$)。
输出
在第一行中打印 $$$q$$$ ($$$0 \leq q \leq 5 \cdot 10^5$$$) — 对的数量。
在接下来的 $$$q$$$ 行中打印两个整数。在第 $$$i$$$ 行中打印 $$$x_i$$$, $$$y_i$$$ ($$$1 \leq x_i, y_i \leq n$$$)。
应满足声明中描述的条件。
如果存在多个答案,您可以打印其中任何一个。
示例
输入 #1
3
输出 #1
1 1 2
输入 #2
4
输出 #2
2 1 2 3 4
注意
在第一个示例中,执行唯一操作后,数组 $$$a$$$ 将是 $$$[f(a_1, a_2), f(a_1, a_2), a_3]$$$。它始终最多有两个不同的数字。
在第二个示例中,执行两次操作后,数组 $$$a$$$ 将变为 $$$[f(a_1, a_2), f(a_1, a_2), f(a_3, a_4), f(a_3, a_4)]$$$。它始终最多有两个不同的数字。