题目描述

有一块 $N\times N$ 的国际象棋棋盘，依次在空格子上放置皇后，最大化放置皇后的数量。你需要构造一组方案。

能在一个格子上放置皇后，当且仅当这个格子被偶数个皇后攻击。

一个皇后攻击一个格子，当且仅当皇后所在的格子与被攻击格子处于同一行/列/对角线上。

输入格式

一行一个整数 $N$。

输出格式

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

接下来 $K$ 行，每行两个整数 $x,y$，描述放置皇后的位置。

输入输出样例 #1

输入 #1

1

输出 #1

1
1 1

输入输出样例 #2

输入 #2

2

输出 #2

1
1 1

输入输出样例 #3

输入 #3

3

输出 #3

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

说明/提示

样例解释

样例 $3$ 解释：

数据范围

对于 $100\%$ 的数据，保证 $1\le N\le 2^{10}$。

子任务编号	分值	约束
$1$	$6$	$1\le N\le 2^4$
$2$	$11$	$1\le N\le 2^6$
$3$	$28$	$1\le N\le 2^8$
$4$	$55$	无额外约束