Description

There is an infinite board. In the lower-left corner, there is a staircase-shaped region of size $n$, and there is a single piece in the very bottom-left cell of this staircase. Each time, you may “split” one piece into two pieces, placing them in the cell one square above and the cell one square to the right of the original position, respectively. (However, if a target cell already contains a piece, you cannot perform this operation.) Your goal is to, after finitely many operations, make the entire staircase contain no pieces. The figure below shows one solution when $n = 2$.

We number rows from bottom to top and columns from left to right, and denote a piece by (row, column), both starting from $1$.

For example, in the third step, the three pieces are at coordinates $(3, 1)$, $(2, 2)$, $(1, 2)$.

Given $n$, you need to output a suitable sequence of operations.

Input Format

Input a single positive integer $n$.

Output Format

If there is a solution, the first line should contain a positive integer $m$, the total number of operations.

In the next $m$ lines, each line contains two positive integers $x_i, y_i$, indicating that in the $i$-th operation you split the piece at row $x_i$, column $y_i$.

If there is no solution, output $-1$ on the first line.

1

1
1 1

2

4
1 1
2 1
2 2
1 2

Hint

• Constraints: For $40\%$ of the testdata, $n \leq 8$.
• Constraints: For $100\%$ of the testdata, $n \leq 1000$.

Translated by ChatGPT 5