L. Least Annoying Constructive Problem
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Consider a complete graph on $$$n$$$ nodes. You have to arrange all its $$$\frac{n(n-1)}{2}$$$ edges on the circle in such a way that every $$$n-1$$$ consecutive edges on this circle form a tree.

It can be proved that such an arrangement is possible for every $$$n$$$. If there are many such arrangements, you can find any of them.

As a reminder, a tree on $$$n$$$ nodes is a connected graph with $$$n-1$$$ edges.

Input

The only line of the input contains a single integer $$$n$$$ $$$(3 \le n \le 500)$$$.

Output

Output $$$\frac{n(n-1)}{2}$$$ lines. The $$$i$$$-th line should contain two integers $$$u_i, v_i$$$ ($$$1 \le u_i \lt v_i \le n$$$). All pairs $$$(u_i, v_i)$$$ have to be distinct, and for every $$$i$$$ from $$$1$$$ to $$$\frac{n(n-1)}{2}$$$, edges $$$(u_i, v_i), (u_{i+1}, v_{i+1}), \ldots, (u_{i + n - 2}, v_{i+n-2})$$$ have to form a tree.

Here $$$u_{\frac{n(n-1)}{2} + i} = u_i, v_{\frac{n(n-1)}{2} + i} = v_i$$$ for every $$$i$$$.

Examples
Input
3
Output
1 2
2 3
1 3
Input
4
Output
1 2
3 4
2 3
1 4
1 3
2 4