Consider a complete graph on 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 . If there are many such arrangements, you can find any of them.
As a reminder, a tree on nodes is a connected graph with n-1 edges.
The only line of the input contains a single integer (3 \le n \le 500).
Output \frac{n(n-1)}{2} lines. The -th line should contain two integers u_i, v_i (1 \le u_i < v_i \le n). All pairs (u_i, v_i) have to be distinct, and for every from 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 .
Example 1
Example 2