Splitting Chess Pieces on a Staircase

There is an infinite chessboard. In its bottom‐left corner, there is a staircase‐shaped region of size \(n\) defined as

\[ S = \{ (r,c) \mid 1 \le r \le n, \; 1 \le c \le n - r + 1 \}, \]

with a single chess piece initially placed in the cell \((1,1)\) (the bottom–left cell of \(S\)). In one move you can take any chess piece from some cell \((r,c)\) and "split" it into two pieces which you place into the cells \((r+1,c)\) and \((r,c+1)\) respectively, provided that both target cells are empty at that moment. (Note that pieces may be split regardless of whether they lie inside \(S\) or not.)

Your task is to provide a sequence of moves (an operation sequence) that, in a finite number of moves, leaves no chess piece in the staircase \(S\). For example, when \(n = 2\) one valid solution is given by performing moves on the pieces in the following order:

\[(1,1) \to \{(2,1), (1,2)\}\; \to\; (2,1) \to \{(3,1),(2,2)\}\; \to\; (2,2) \to \{(3,2),(2,3)\}\; \to\; (1,2) \to \{(2,2),(1,3)\}\, ,\]

After these moves the pieces lie in \((3,1),(3,2),(2,3),(2,2),(1,3)\), so that none of the cells of \(S = \{(1,1),(1,2),(2,1)\}\) is occupied. Rows are numbered from bottom to top and columns from left to right, both starting at 1.

Input and Output Formats: The input is a single integer \(n\) and the output should first state the number \(m\) of moves performed, followed by \(m\) lines. Each of these lines should contain two integers \(r\) and \(c\) meaning that the chess piece in cell \((r,c)\) is chosen to be split (i.e. it is removed and replaced by two pieces at \((r+1,c)\) and \((r,c+1)\)).

Note: A valid sequence is not necessarily unique. It is guaranteed that a solution always exists.

inputFormat

The input consists of a single integer \(n\) (e.g. \(1 \le n \le 10\)) which determines the size of the staircase region.

outputFormat

First output an integer \(m\) indicating the number of moves. Then output \(m\) lines, each line containing two integers \(r\) and \(c\). A move on \((r,c)\) means that the chess piece at \((r,c)\) is split into two pieces placed at \((r+1,c)\) and \((r,c+1)\) respectively.

sample

1

1
1 1