给你一个正整数$$$n$$$。
在此问题中,整数集合 $$$c_1,c_2,\dots,c_k$$$ 的 $$$\operatorname{MEX}$$$ 被定义为集合 $$$c$$$ 中不出现的最小正整数 $$$x$$$。
数组 $$$a_1,\dots,a_n$$$ 的素数定义为 $$$(l,r)$$$ 的对数,使得 $$$1 \le l \le r \le n$$$ 和 $$$\operatorname{MEX}(a_l,\dots,a_r)$$$ 是素数。
在 $$$1,2,\dots,n$$$ 的所有排列中找到具有最大可能素数的 $$$1,2,\dots,n$$$ 的任何排列。
注意:
- 素数是大于或等于 $$$2$$$ 且不能被除 $$$1$$$ 及其本身之外的任何正整数整除的数字。例如,$$$2,5,13$$$ 是质数,但 $$$1$$$ 和 $$$6$$$ 不是质数。
- $$$1,2,\dots,n$$$ 的排列是一个由 $$$n$$$ 不同整数组成的数组,从 $$$1$$$ 到 $$$n$$$ 的任意顺序。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$n=3$$$但数组中有$$$4$$$)。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的唯一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$)。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出 $$$n$$$ 整数:$$$1,2,\dots,n$$$ 的排列,实现最大可能的素数。
如果有多个解决方案,请打印其中任何一个。
示例
输入 #1
3 2 1 5
输出 #1
2 1 1 5 2 1 4 3
注意
在第一个测试用例中,有 $$$3$$$ 对 $$$(l,r)$$$ 与 $$$1 \le l \le r \le 2$$$,其中 $$$2$$$ 有素数 $$$\operatorname{MEX}(a_l,\dots,a_r)$$$:
- $$$(l,r) = (1,1)$$$: $$$\operatorname{MEX}(2) = 1$$$,不是素数。
- $$$(l,r) = (1,2)$$$: $$$\operatorname{MEX}(2,1) = 3$$$,这是素数。
- $$$(l,r) = (2,2)$$$: $$$\operatorname{MEX}(1) = 2$$$,这是素数。
在第二个测试用例中,$$$\operatorname{MEX}(1) = 2$$$ 是素数,因此素数是 $$$1$$$。
在第三个测试用例中,最大可能的素数是 $$$8$$$。