While creating data for problem D: ㄷㄷㄷㅈ, the UCPC problem setters realized that it is difficult to construct a DUDUDUNGA-tree with many vertices. Given $N$, let's write a program that outputs a DUDUDUNGA-tree with $N$ vertices.

Input

The first line contains the number of vertices $N$ of the tree. ($6 \le N \le 300\,000$)

Output

Output $N-1$ lines, each containing the two endpoints of an edge, separated by a space. The vertex numbers must be integers between $1$ and $N$.

Examples

Input 1

6

Output 1

1 2
2 3
3 4
4 5
4 6

Note

Refer to problem D: ㄷㄷㄷㅈ for the definition of a DUDUDUNGA-tree. For any given $N$, a DUDUDUNGA-tree with $N$ vertices always exists.