题目描述

给定正整数 $n$（$n \ge 3$），你需要构造一棵 $n$ 个节点的树，点有点权，使之满足如下要求：

1. 对于任一节点，其点权为不超过 $11000$ 的正整数。
2. 对于任一不大于 $n$ 的正整数 $k$，都存在树上的一条长度不小于 $1$ 的链，使得该链上所有点权的最大公约数为 $k$。

其中链的长度定义为其经过的边数。

在本题的数据范围内答案一定存在，如果有多种构造方案，输出任意一组即可。

---

输入格式

输入一行一个正整数 $n$。

---

输出格式

输出共 $n$ 行。

• 第一行输出 $n$ 个正整数，其中第 $i$ 个数表示你构造的树上节点 $i$ 的点权。
• 接下来 $n - 1$ 行，每行包含两个正整数 $u$ 和 $v$，表示你构造的树上有一条连接 $u$ 和 $v$ 的边。

输出任意一组构造方案即可。

---

样例 1

输入：

3

输出：

2 6 3
1 2
2 3

---

样例 2

输入：

4

输出：

3 6 8 12
1 2
2 3
3 4

---

样例 3

输入：

5

输出：

10 15 6 8 4
1 2
2 3
3 4
4 5

---

数据范围与提示

共 $25$ 个测试点，每个测试点 $4$ 分。

对于所有数据，$3 \le n \le 2500$。

测试点编号	$n$ 范围
1~2	$\le 10$
3	$=32$
4	$=64$
5~7	$\le 100$
8~10	$\le 200$
11~13	$\le 400$
14~16	$\le 800$
17~18	$\le 1200$
19~21	$\le 1600$
22~23	$\le 2000$
24~25	$\le 2500$