CF1562F.Tubular Bells

Do you know what tubular bells are? They are a musical instrument made up of cylindrical metal tubes. In an orchestra, tubular bells are used to mimic the ringing of bells.

Mike has tubular bells, too! They consist of $n$ tubes, and each of the tubes has a length that can be expressed by a integer from $l$ to $r$ inclusive. It is clear that the lengths of all the tubes are different (it makes no sense to make the same tubes). It is also known that $r-l+1 = n$.

Formally, we can say that Mike's tubular bells are described by a permutation $a$ of length $n$ that contains all numbers from $l$ to $r$ inclusive, with $a_i$ denoting the length of the $i$-th tube.

You are offered an interesting task: to guess what Mike's instrument looks like. Simply, you must guess the permutation.

Mike won't tell you $l$ or $r$. He will only tell you $n$, and will allow you to ask no more than $n + 5000$ queries.

In each query, you name two positive integers $x$, $y$ such that $1 \le x, y \le n, x \neq y$. In response to this query, the program written by Mike will give you $\mathrm{lcm}(a_x, a_y)$, where $\mathrm{lcm}(c,d)$ denotes the least common multiple of $c$ and $d$.

Solve Mike's problem!

你知道管钟（tubular bells）吗？它是一种由圆柱形金属管构成的乐器。在管弦乐队中，管钟被用来模拟钟声。

迈克也有一套管钟！它由 $n$ 根管子组成，每根管子的长度均为一个介于 $l$ 到 $r$（含端点）之间的整数。显然，所有管子的长度互不相同（制作完全相同的管子毫无意义）。此外，已知 $r - l + 1 = n$。

形式化地说，迈克的管钟可用一个长度为 $n$ 的排列 $a$ 来描述，该排列恰好包含从 $l$ 到 $r$（含端点）的所有整数，其中 $a_i$ 表示第 $i$ 根管子的长度。

现在你面临一项有趣的任务：推断出迈克的管钟长什么样。换句话说，你需要猜出这个排列 $a$。

迈克不会告诉你 $l$ 或 $r$ 的值。他只会告诉你 $n$，并允许你最多进行 $n + 5000$ 次询问。

每次询问中，你需要指定两个正整数 $x$、$y$，满足 $1 \le x, y \le n$ 且 $x \ne y$。作为回应，迈克编写的程序将返回 $\mathrm{lcm}(a_x, a_y)$，其中 $\mathrm{lcm}(c,d)$ 表示 $c$ 与 $d$ 的最小公倍数。

请解决迈克提出的问题！

Each test contains multiple test cases.

The first line contains one positive integer $t$ ($1 \le t \le 20$), denoting the number of test cases. Description of the test cases follows.

The single line of each test case contains one positive integer $n$ ($3 \le n \le 10^5$) — number of tubes in Mike's tubular bells. Also $1 \le l \le r \le 2 \cdot 10^5$, i.e. the lengths of the tubes do not exceed $2 \cdot 10^5$.

It is guaranteed that the sum of maximal number of queries (i.e. $n + 5000$) over all test cases does not exceed $10^5 + 5000$. It means that sum of $n$ does not exceed $10^5 + 5000 - t \cdot 5000$.

每个测试包含多个测试用例。

第一行包含一个正整数 $t$（$1 \le t \le 20$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例仅有一行，包含一个正整数 $n$（$3 \le n \le 10^5$）——即 Mike 的管钟所含管子的数量。此外，满足 $1 \le l \le r \le 2 \cdot 10^5$，即管子的长度不超过 $2 \cdot 10^5$。

保证所有测试用例中最大查询次数之和（即 $n + 5000$ 之和）不超过 $10^5 + 5000$。这意味着所有测试用例中 $n$ 的总和不超过 $10^5 + 5000 - t \cdot 5000$。