Problem Description

There is an $ N $ × $ N $ chessboard.

The square that is $ i $ squares to the right and $ j $ squares down from the top-left square is called $(i,\ j)$. In particular, the top-left square is $(0,\ 0)$.

The squares $(i,\ j)$ where $ i + j $ is even are painted black, and the others are painted white.

We will now repaint some of the white squares to black to satisfy the following condition:

• Starting from the square $(0,\ 0)$, it is possible to reach all black squares by repeatedly moving to adjacent black squares that share an edge.

Repaint no more than $ 170000 $ squares to black to achieve this condition.

Input Format

The input is given from the standard input in the following format:

$ N $

Output Format

Output the information of the squares repainted to black in the following format:

$ K $ $ x_1 $ $ y_1 $ $ x_2 $ $ y_2 $ $ : $ $ x_K $ $ y_K $

This indicates that a total of $ K $ squares were repainted to black, and the $ i $-th square repainted was $(x_i,\ y_i)$.

Sample Input and Output

Sample Input #1

2

Sample Output #1

1
1 0

Sample Input #2

4

Sample Output #2

3
0 1
2 1
2 3

Notes/Hints

Constraints

• $1 \leq N \leq 1,000$

Judging

The output is considered correct only if all the following conditions are met:

• $0 \leq K \leq 170000$
• $0 \leq x_i,\ y_i \leq N-1$
• For all $ i $, $ x_i + y_i $ is odd.
• If $i \neq j$, then $(x_i,\ y_i) \neq (x_j,\ y_j)$
• The condition in the problem statement is achieved by repainting all the squares outputted to black.

见题面 Input 部分

见题面 Output 部分