Problem 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, and queens are placed sequentially on empty squares to maximize the number of queens placed. You need to construct a solution.

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

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

Input Format

A single line containing an integer $N$.

Output Format

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

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

Sample Input and Output

Sample Input #1

1

Sample Output #1

1
1 1

Sample Input #2

2

Sample Output #2

1
1 1

Sample Input #3

3

Sample Output #3

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

Notes

Sample Explanation

Sample $3$ Explanation:

Data Range

For $100\%$ of the data, $1 \le N \le 2^{10}$.

见题面 Input 部分

见题面 Output 部分