题目描述

先定义树中的两类四点结构。

从一棵树中选出四个不同顶点，只保留这四个顶点之间原本存在的边。若得到的图仍连通，则它必然是下面两种树之一：

D 型

四个顶点构成一条长度为 $3$ 的链：

●—●—●—●

G 型

一个中心顶点与另外三个顶点相连：

  ●
  |
●—●—●

记树中 D 型四点集合的数量为 $D$，G 型四点集合的数量为 $G$。

若

则称这棵树为一棵 DUDUDUNGA 树。

UCPC 出题组在为原题《DUDUDUNGA》制作数据时发现，构造顶点很多的 DUDUDUNGA 树并不容易。

现在给定 $N$，请输出一棵恰好包含 $N$ 个顶点的 DUDUDUNGA 树。

输入格式

第一行包含一个整数 $N$，表示树的顶点数。

输出格式

输出 $N-1$ 行，每行包含两个整数 $u,v$，表示树中有一条连接顶点 $u$ 与顶点 $v$ 的边。

所有顶点编号必须是 $1$ 到 $N$ 之间的整数。

只要输出任意一棵满足要求的树即可。

数据范围

保证对于每个合法的 $N$，都至少存在一棵包含 $N$ 个顶点的 DUDUDUNGA 树。

样例

输入

6

输出

1 2
2 3
3 4
4 5
4 6