海龟刚刚在数学课上学会了如何将两个整数相乘,他非常兴奋。
然后小猪给了他一个整数$$$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]$$$ 满足条件,但其不同元素的数量不是最小的。