题目描述

有一个 $N\times N$ 的棋盘。你希望在棋盘上放置尽可能多的皇后，并且整个放置过程必须满足如下规则：

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

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

输入格式

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

输出格式

第一行输出一个整数 $K$，表示最多能够放置的皇后数量。

接下来 $K$ 行，每行输出两个整数 $R_i,S_i$，表示第 $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 解释