非官方翻译，来自 Qingyu。

有一个 $N \times N$ 的棋盘，你想要在上面放置尽可能多的皇后，并遵守以下规则：

• 一个位置可以放置皇后，当且仅当其没有被任何皇后覆盖，且能被恰好偶数个皇后所攻击到。

注意：皇后可以攻击所有与它在同一行、同一列或同一个对角线上的位置。

输入格式

输入只有一行，包含一个整数 $N$。

输出格式

输出的第一行包含一个整数 $K$，表示所能放置的皇后数量的最大值。

接下来 $K$ 行，每行两个整数 $R_i, S_i$，描述这一步将皇后放置在格子 $(R_i, S_i)$ 上。

如果有多种合法的方案，你可以输出任意一种。

子任务

样例数据

样例 1 输入

1

样例 1 输出

1
1 1

样例 2 输入

2

样例 2 输出

1
1 1

样例 3 输入

3

样例 3 输出

9
2 3
3 1
2 2
1 1
3 3
3 2
1 2
1 3
2 1

样例 3 解释