Description

Input

The only line of input contains one integer $n$ ($1 \le n \le 10^{3}$) — number of knights in the initial placement.

Output

Print $n$ lines. Each line should contain $2$ numbers $x_{i}$ and $y_{i}$ ($-10^{9} \le x_{i}, \,\, y_{i} \le 10^{9}$) — coordinates of $i$-th knight. For all $i \ne j$, $(x_{i}, \,\, y_{i}) \ne (x_{j}, \,\, y_{j})$ should hold. In other words, all knights should be in different cells.

It is guaranteed that the solution exists.

4

1 1
3 1
1 5
4 4

7

2 1
1 2
4 1
5 2
2 6
5 7
6 6

Note

Let's look at second example:

Green zeroes are initial knights. Cell $(3, \,\, 3)$ is under attack of $4$ knights in cells $(1, \,\, 2)$, $(2, \,\, 1)$, $(4, \,\, 1)$ and $(5, \,\, 2)$, therefore Ivan will place a knight in this cell. Cell $(4, \,\, 5)$ is initially attacked by only $3$ knights in cells $(2, \,\, 6)$, $(5, \,\, 7)$ and $(6, \,\, 6)$. But new knight in cell $(3, \,\, 3)$ also attacks cell $(4, \,\, 5)$, now it is attacked by $4$ knights and Ivan will place another knight in this cell. There are no more free cells which are attacked by $4$ or more knights, so the process stops. There are $9$ knights in the end, which is not less than $\lfloor \frac{7^{2}}{10} \rfloor = 4$.