Background

Translated from Izborne Pripreme 2022 (Croatian IOI/CEOI Team Selection) D1T1。$\texttt{1s,0.5G}$。

Problem Description

There is an $N \times N$ chessboard. Place queens on empty squares one by one, maximizing the number of queens placed. You need to construct a valid plan.

A queen can be placed on a square if and only if that square is attacked by an even number of queens.

A queen attacks a square if and only if the queen's square and the attacked square are in the same row, column, or diagonal.

Input Format

One line with an integer $N$。

Output Format

The first line contains an integer $K$, the maximum number of queens that can be placed.

The next $K$ lines each contain two integers $x, y$, describing the position where a queen is placed.

1

1
1 1

2

1
1 1

3

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

Hint

Sample Explanation

Explanation for sample $3$：

Constraints

For $100\%$ of the data, it is guaranteed that $1 \le N \le 2^{10}$。

Translated by ChatGPT 5