F. A Simple Construction Problem
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given an integer $$$n$$$, construct a permutation $$$p_1,p_2,\ldots,p_n$$$ of $$$1,2,\ldots,n$$$ such that the sum of every pair of adjacent elements is not a perfect square. In other words, for every $$$1\le i \lt n$$$, there does not exist an integer $$$x$$$ such that

$$$p_i+p_{i+1}=x^2$$$.

It can be proven that an answer exists for every valid $$$n$$$.

Input

The first line contains an integer $$$T$$$, the number of test cases.

Each of the next $$$T$$$ ($$$1\le T \le10^4$$$) lines contains one integer $$$n$$$ ($$$1\le n \le 4 \cdot 10^6$$$)

and the sum of $$$n$$$ over all test cases does not exceed $$$4\cdot 10^6$$$.

Output

For each test case, output one line containing a permutation satisfying the condition.

If there are multiple valid answers, output any of them.

Example
Input
5
1
2
3
4
5
Output
1
1 2
1 2 3
1 2 3 4
1 4 2 3 5