Vasylko 得到了写有数字 $1$ 到 $n$ 的立方体。其中，有 $1$ 个立方体写着数字 $n$，$2$ 个立方体写着数字 $n-1$，依此类推，有 $n-1$ 个立方体写着数字 $2$，$n$ 个立方体写着数字 $1$。

他将这些立方体放置在一个没有顶边界的正方形框架中，使得所有立方体都位于从左上角到右下角的对角线下方。在左侧的第一列中，有 $n$ 个写着数字 $1$ 的立方体；在第二列中，有 $n-1$ 个写着数字 $2$ 的立方体……在第 $n$ 列中，有 $1$ 个写着数字 $n$ 的立方体。也就是说，在第 $i$ 列中，有 $n-i+1$ 个写着数字 $i$ 的立方体。

初始状态

Vasylko 想要重新排列它们，使得所有立方体都位于另一条对角线（副对角线）下方。因此，在自底向上的第一行中，应该有 $n$ 个写着数字 $1$ 的立方体；在第二行中，应该有 $n-1$ 个写着数字 $2$ 的立方体……在第 $n$ 行中，应该有 $1$ 个写着数字 $n$ 的立方体。也就是说，在第 $i$ 行中，应该有 $n-i+1$ 个写着数字 $i$ 的立方体。

最终状态

他还决定，他只能将立方体从某一列的顶部移动到另一列的顶部（不一定相邻）。请帮助他以最有效的方式完成这一操作——找到他所需的最少移动次数，并输出 Vasylko 应该进行的移动步骤。

你可以获得部分分，详情见下文。

输入格式

第一行包含一个整数 $n$ ($3 \le n \le 1000$) —— 正方形的大小。

输出格式

第一行输出一个整数 $k$ ($1 \le k \le 10^6$) —— 重新排列立方体所需的最少移动次数。

在接下来的 $k$ 行中，每行输出两个整数 $a$ 和 $b$ ($1 \le a, b \le n$; $a \ne b$)，其中 $a$ 是你取出立方体的列号，$b$ 是你放置立方体的列号。

子任务

• 1. (12 分): $n = 4$;
• 2. (20 分): $n = 5$;
• 3. (20 分): $n = 6$;
• 4. (20 分): $n \le 10$;
• 5. (20 分): $n \le 100$;
• 6. (8 分): 无附加限制。

对于每个测试点块（子任务），如果你对该块中的每个测试点都输出了正确的 $k$，你可以获得该块一半的分数。如果你输出的 $k$ 不正确，但移动指令是正确的，你将获得该块四分之一的分数；在这种情况下，要求 $k \le 10^6$。

请注意，要获得一半的分数，你需要输出正确的 $k$，并且：

• 要么不输出其他任何内容；即仅输出 $k$，不输出任何指令；
• 要么完整输出所有 $k$ 条指令，其中所有列号都在 $1$ 到 $n$ 之间。对这些指令没有其他正确性要求。

如果你输出的指令数量不等于 $k$（例如，只输出了几条指令，或者输出了太多指令），或者输出了不属于列号的数字等，你将获得 0 分。

样例不提供部分分，其分值为 0 分。

当 $n = 3$ 时，获得一半分数的输出可能如下所示：

8

或者如下所示：

8
1 2
2 1
1 2
2 1
1 2
2 1
1 2
2 1

当 $n = 3$ 时，获得四分之一分数的输出可能如下所示：

10
1 3
3 1
3 2
1 3
2 1
2 3
1 3
2 3
1 2
3 2

如果你输出的指令数量不等于 $k$，你将获得 0 分：

8
1 3
3 1
3 2
1 3
2 1
2 3
1 3
2 3
1 2
3 2

样例

输入样例 1

3

输出样例 1

8
3 2
1 3
2 1
2 3
1 3
2 3
1 2
3 2

说明

首先，我们将放置最后一列。因此，在最少移动次数下，重新排列立方体的唯一第一步可能是将 $3$ 从第三列移动到第二列，因为如果我们不移动 $3$ 或者不把它移动到第二列，我们将无法在第三列的开头放置 $1$。

前 3 个状态

在我们放置了 $1$ 之后，我们需要将 $2$ 和 $3$ 放置在第三列的对应位置上。同样，唯一的办法是先将 $3$ 移动到第一列，因为否则我们在下一步中将无法在第三列中放置 $2$，然后再将 $3$ 放置到它的位置上。

接下来的 3 个状态

在此之后，我们希望正确放置第二列。为了让 $1$ 成为第一个数字，我们首先需要拿走 $2$，而我们只能将其放入最后一列。在放置了 $1$ 之后，我们只需要将 $2$ 放回第二列，即可达到立方体所需的最终状态。

最后 3 个状态