考虑一个包含 $n$ 个节点的完全图。你需要将它的所有 $\frac{n(n-1)}{2}$ 条边排列在一个圆上，使得圆上每 $n-1$ 条连续的边都能构成一棵树。

可以证明，对于任意 $n$，这样的排列都是存在的。如果存在多种这样的排列，你可以输出其中任意一种。

作为提醒，一个包含 $n$ 个节点的树是一个拥有 $n-1$ 条边的连通图。

输入格式

输入仅包含一行，为一个整数 $n$ ($3 \le n \le 500$)。

输出格式

输出 $\frac{n(n-1)}{2}$ 行。第 $i$ 行应包含两个整数 $u_i, v_i$ ($1 \le u_i < v_i \le n$)。所有数对 $(u_i, v_i)$ 必须互不相同，且对于从 $1$ 到 $\frac{n(n-1)}{2}$ 的每一个 $i$，边 $(u_i, v_i), (u_{i+1}, v_{i+1}), \dots, (u_{i+n-2}, v_{i+n-2})$ 必须构成一棵树。

这里对于每一个 $i$，满足 $u_{\frac{n(n-1)}{2}+i} = u_i$，$v_{\frac{n(n-1)}{2}+i} = v_i$。

样例

样例输入 1

3

样例输出 1

1 2
2 3
1 3

样例输入 2

4

样例输出 2

1 2
3 4
2 3
1 4
1 3
2 4