← 返回题目列表

Codeforces · 1981/D

D. 海龟和乘法

中文机器翻译题面 查看原题

海龟刚刚在数学课上学会了如何将两个整数相乘,他非常兴奋。

然后小猪给了他一个整数$$$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 找到具有最少数量的不同元素的序列。

乌龟肯定解决不了这个问题,所以请帮助他!

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$ 的元素。

如果有多个答案,请打印其中任何一个。

示例

输入 #1

3
2
3
4

输出 #1

114514 114514
1 2 2
3 3 4 4

注意

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