A. Zigzag Parity
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an integer $$$n$$$.

Construct a permutation $$$p$$$ of length $$$n$$$ such that for each $$$i$$$ $$$(1 \le i \le n-2)$$$, $$$(a_i+a_{i+1}) \mod 2 \neq (a_{i+1} + a_{i+2}) \mod 2$$$.

It is guaranteed that the answer always exists.

Input

The first line contains a single integer $$$tc \: (1 \le tc \lt 1000)$$$ — the number of testcases.

The only line of each testcase contains a single integer $$$n \: (1 \le n \le 5\cdot 10^5)$$$.

It is guaranteed that the sum of $$$n$$$ over all the testcases doesn't exceed $$$5 \cdot 10^5$$$.

Output

For each testcase, print a permutation $$$p$$$.

If there are multiple answers, print any.

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