You are given a positive integer $$$n$$$.
In this problem, the $$$\operatorname{MEX}$$$ of a collection of integers $$$c_1,c_2,\dots,c_k$$$ is defined as the smallest positive integer $$$x$$$ which does not occur in the collection $$$c$$$.
The primality of an array $$$a_1,\dots,a_n$$$ is defined as the number of pairs $$$(l,r)$$$ such that $$$1 \le l \le r \le n$$$ and $$$\operatorname{MEX}(a_l,\dots,a_r)$$$ is a prime number.
Find any permutation of $$$1,2,\dots,n$$$ with the maximum possible primality among all permutations of $$$1,2,\dots,n$$$.
Note:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.
The only line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, output $$$n$$$ integers: a permutation of $$$1,2,\dots,n$$$ that achieves the maximum possible primality.
If there are multiple solutions, print any of them.
3215
2 1 1 5 2 1 4 3
In the first test case, there are $$$3$$$ pairs $$$(l,r)$$$ with $$$1 \le l \le r \le 2$$$, out of which $$$2$$$ have a prime $$$\operatorname{MEX}(a_l,\dots,a_r)$$$:
In the second test case, $$$\operatorname{MEX}(1) = 2$$$ is prime, so the primality is $$$1$$$.
In the third test case, the maximum possible primality is $$$8$$$.
Name |
---|