H. Dilworth's Theorem
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a positive integer $$$n$$$. Construct a permutation $$$p$$$ of $$$\{1,2,\ldots,n\}$$$ such that the length of the longest increasing subsequence of $$$p$$$ is equal to the length of the longest decreasing subsequence of $$$p$$$.

An increasing (decreasing) subsequence of an array $$$a$$$ of length $$$n$$$ is defined as an array $$$b$$$ such that:

  • $$$1 \le b_1 \lt b_2 \lt \ldots \lt b_m \le n$$$.
  • $$$a_{b_1} \lt a_{b_2} \lt \ldots \lt a_{b_m}$$$ ($$$a_{b_1} \gt a_{b_2} \gt \ldots \gt a_{b_m}$$$).
Input

Each test contains multiple test cases. The first line of each test contains an integer $$$t$$$ ($$$1 \le t \le 5 \cdot 10^4$$$) — the number of test cases.

The only line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of $$$p$$$ to be constructed.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, if no solution exists, output $$$-1$$$ on a single line.

Otherwise, output $$$n$$$ distinct integers $$$p_1,p_2,\ldots,p_n$$$ ($$$1 \le p_i \le n$$$) on a single line — the permutation $$$p$$$ you constructed.

If multiple solutions exist, you may output any of them.

Example
Input
1
3
Output
3 1 2