CF1981D.Turtle and Multiplication

Turtle 刚刚在数学课上学会了如何将两个整数相乘，他感到非常兴奋。

然后 Piggy 给了他一个整数 $n$，并要求他构造一个由整数组成的序列 $a_1, a_2, \ldots, a_n$，使其满足以下条件：

• 对于所有 $1 \le i \le n$，都有 $1 \le a_i \le 3 \cdot 10^5$。
• 对于所有 $1 \le i < j \le n - 1$，都有 $a_i \cdot a_{i + 1} \ne a_j \cdot a_{j + 1}$。

在所有满足条件的序列中，Piggy 要求 Turtle 找出不同元素数量最少的那一个。

Turtle 显然无法解决这个问题，所以请你帮帮他吧！

每个测试点包含多组测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 10^6$），表示序列 $a$ 的长度。

保证所有测试用例中 $n$ 的总和不超过 $10^6$。

对于每个测试用例，输出 $n$ 个整数 $a_1, a_2, \ldots, a_n$，表示序列 $a$ 的元素。

如果有多种答案，输出任意一种即可。

在第三个测试用例中，$a = [3, 4, 2, 6]$ 不满足第二个条件，因为 $a_1 \cdot a_2 = a_3 \cdot a_4$。$a = [2, 3, 4, 4]$ 虽然满足条件，但其不同元素的数量不是最少的。

由 ChatGPT 4.1 翻译