You are given an $N \times N$ chessboard. Determine the maximum number of queens that can be placed on the board, following this rule:
A queen may be placed on any empty square that is currently attacked by an even number of already placed queens.
Note: Once placed on the board, a queen attacks all squares in the same row, column, and diagonals.
Input
The first and only line contains a natural number $N$, the dimensions of the chessboard.
Output
In the first line, print a natural number $K$, the maximum number of queens that can be placed on the board following the given rule.
In the $i$-th of the next $K$ lines, print the natural numbers $R_i$ and $S_i$, the row and column where the $i$-th queen is placed.
If there are multiple ways to place the queens, print any one of them.
Subtasks
| Subtask | Points | Constraints |
|---|---|---|
| 1 | 6 | $1 \le N \le 16$ |
| 2 | 11 | $1 \le N \le 64$ |
| 3 | 28 | $1 \le N \le 256$ |
| 4 | 55 | $1 \le N \le 1024$ |
Examples
Input 1
1
Output 1
1 1 1
Input 2
2
Output 2
1 1 1
Input 3
3
Output 3
9 2 3 3 1 2 2 1 1 3 3 3 2 1 2 1 3 2 1
Note
Explanation of the third example: