考虑如下任务：给定一棵具有 $n$ ($n \ge 1$) 个顶点的树（无环连通无向图）。你需要计算用 $n$ 种颜色对该树的顶点进行合法染色的方案数。如果任意两个距离不超过两条边的顶点颜色均不相同，则称该染色方案是合法的。如果两个染色方案中存在至少一个顶点颜色不同，则认为这两个染色方案是不同的。由于方案数可能非常大，你需要输出其对 $10^9 + 7$ 取模后的结果。

你的任务是解决逆问题：给定区间 $[1, 10^9 + 6]$ 中的一个数 $r$，找到任意一棵顶点数最少的树，使得上述问题的答案为 $r$。可以证明，对于给定范围内的每一个可能的数 $r$，至少存在一棵这样的树。

输入格式

输入的第一行包含一个整数 $t$ ($1 \le t \le 10$)，表示测试用例的数量。

接下来的 $t$ 行，每行包含一个整数。第 $i$ 行的数字为 $r_i$ ($1 \le r_i \le 10^9 + 6$)。所有 $r_i$ 的值互不相同。

输出格式

输出应包含 $t$ 个数据块：第 $i$ 个数据块应包含第 $i$ 个测试用例的答案。

描述树的数据块应以一行包含一个正整数 $n_i$ 开头，表示树的顶点数。

接下来的 $n_i - 1$ 行，每行包含两个整数。第 $j$ 行的数字 $a_{i,j}$ 和 $b_{i,j}$ ($1 \le a_{i,j}, b_{i,j} \le n_i$) 表示连接顶点 $a_{i,j}$ 和 $b_{i,j}$ 的边。树的顶点编号为 $1$ 到 $n_i$。如果存在多棵顶点数最少且染色方案数对 $10^9 + 7$ 取模后等于 $r_i$ 的树，你可以输出其中任意一棵。

样例

输入 1

4
2
360
1
509949433

输出 1

2
1 2
5
1 2
2 3
3 4
3 5
1
10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10

说明

在最后一个测试用例中，树的染色方案数为 $1509949440$，其对 $10^9 + 7$ 取模的结果为 $509949433$。