Problem Description

There is an infinite chessboard with a staircase-shaped region of size $n$ at the bottom left corner, where the bottom-left cell contains a chess piece. You can "split" a chess piece into two pieces, placing one in the cell above and one in the cell to the right of the original position (but you cannot do this if the target positions already contain pieces). Your goal is to remove all chess pieces from the staircase region through a finite number of operations. The figure below shows a solution for $n = 2$.

Rows are numbered from bottom to top, and columns are numbered from left to right, both starting from 1. Chess pieces are marked with coordinates (row, column).

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

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

Input Format

Input consists of a single positive integer $n$.

Output Format

If a solution exists, the first line should contain a positive integer $m$, representing the total number of operations needed.

The following $m$ lines each contain two positive integers $x_i, y_i$, indicating that the piece at the $x_i$-th row and $y_i$-th column is split in the $i$-th operation.

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

Sample Input and Output

Sample Input #1

1

Sample Output #1

1
1 1

Sample Input #2

2

Sample Output #2

4
1 1
2 1
2 2
1 2

Notes

• For $40\%$ of the data: $n \leq 8$;
• For $100\%$ of the data: $n \leq 1000$.

见题面 Input 部分

见题面 Output 部分