对于整数序列$$$a = [a_1, a_2, \ldots, a_n]$$$,我们将$$$f(a)$$$定义为$$$a$$$的最长子序列$$$^{\text{*}}$$$的长度,该子序列是回文$$$^{\text{†}}$$$。
让 $$$g(a)$$$ 表示长度为 $$$f(a)$$$ 的回文子序列的数量。换句话说,$$$g(a)$$$ 计算$$$a$$$ 中具有最大长度的回文子序列的数量。
给定一个整数 $$$n$$$,你的任务是找到满足以下条件的 $$$n$$$ 整数的任何序列 $$$a$$$:
- $$$1 \le a_i \le n$$$ 对于所有 $$$1 \le i \le n$$$。
- $$$g(a) > n$$$
可以证明,在给定的约束下,这样的序列总是存在。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 100$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$\color{red}{6} \le n \le 100$$$) — 序列的长度。
请注意,所有测试用例的 $$$n$$$ 总和没有限制。
输出
对于每个测试用例,输出 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$,表示满足条件的数组。
如果有多个解,则可以输出其中任何一个。
示例
输入 #1
3 6 9 15
输出 #1
1 1 2 3 1 2 7 3 3 7 5 3 7 7 3 15 8 8 8 15 5 8 1 15 5 8 15 15 15 8
注意
在第一个示例中,一个可能的解决方案是 $$$a = [1, 1, 2, 3, 1, 2]$$$。在这种情况下,$$$f(a) = 3$$$,因为最长回文子序列的长度为 $$$3$$$。有 $$$7$$$ 方法可以选择长度为 $$$3$$$ 的回文子序列,如下所示:
1.$$$[a_1, a_2, a_5] = [1, 1, 1]$$$
2.$$$[a_1, a_3, a_5] = [1, 2, 1]$$$
3.$$$[a_1, a_4, a_5] = [1, 3, 1]$$$
4.$$$[a_2, a_3, a_5] = [1, 2, 1]$$$
5.$$$[a_2, a_4, a_5] = [1, 3, 1]$$$
6.$$$[a_3, a_4, a_6] = [2, 3, 2]$$$
7. $$$[a_3, a_5, a_6] = [2, 1, 2]$$$
因此,$$$g(a) = 7$$$,大于 $$$n = 6$$$。因此,$$$a = [1, 1, 2, 3, 1, 2]$$$ 是一个有效的解决方案。
在第二个示例中,一种可能的解决方案是 $$$a = [7, 3, 3, 7, 5, 3, 7, 7, 3]$$$。在这种情况下,$$$f(a) = 5$$$。有 $$$24$$$ 方法可以选择长度为 $$$5$$$ 的回文子序列。一些示例是 $$$[a_2, a_4, a_5, a_8, a_9] = [3, 7, 5, 7, 3]$$$ 和 $$$[a_1, a_4, a_6, a_7, a_8] = [7, 7, 3, 7, 7]$$$。因此,$$$g(a) = 24$$$,大于$$$n = 9$$$。因此, $$$a = [7, 3, 3, 7, 5, 3, 7, 7, 3]$$$ 是一个有效的解决方案。
在第三个示例中,$$$f(a) = 7$$$ 且 $$$g(a) = 190$$$,大于 $$$n = 15$$$。