题目描述

小乌龟刚刚在他的数学课上学会了如何做乘法，他很兴奋。于是，小猪给了他一个正整数 $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$，保证 $a_i\cdot a_{i+1}\ne a_j\cdot a_{j+1}$。

满足这两个条件的序列显然有很多，小猪要求小乌龟找到其中 不同元素最少 的那一个构造。

小乌龟自己解决不了这个问题了，请你帮帮他吧！

输入格式

第一行一个正整数 $t\ (1\le t\le 10^4)$，代表该测试点的数据组数。

接下来 $t$ 行每行一个正整数 $n\ (2\le n\le 10^6)$ 为一组数据，表示这组数据中小猪要求小乌龟构造的序列的长度。保证在一个测试点中，所有的 $n$ 之和不超过 $10^6$。

输出格式

输出一共 $t$ 行，每行输出该组数据中 $n$ 对应的序列 $a_1,a_2,\ldots,a_n$，表示小乌龟应当给出的构造。如果有多个解，请你输出任意一个。

样例 #1

样例输入 #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]$ 满足了所有限制，但是它含有三个不同元素，不能使得不同元素个数最少（$a = [3, 3, 4, 4]$ 只有两个不同元素）。