Given a positive integer $n$, construct a permutation $p_1, p_2, \dots, p_n$ of $1$ to $n$ such that the following condition is satisfied:

• For $1 \le i \le n$, let $c_i = \lceil \frac{p_1+p_2+\dots+p_i}{i} \rceil$. Then at least $\lfloor \frac{n}{3} \rfloor - 1$ of the values $c_1, c_2, \dots, c_n$ are prime numbers.

There are multiple test cases. The first line contains an integer $t$ ($1 \le t \le 10$) representing the number of test cases. Each test case is described as follows:

Each test case consists of a single line containing an integer $n$ ($2 \le n \le 10^5$).

For each test case, output any permutation $p_1, p_2, \dots, p_n$ that satisfies the given conditions. It is guaranteed that such a permutation exists.

Examples

Input 1

2
2
3

Output 1

2 1
2 1 3

Note

For the first test case, we have $c_1 = \lceil \frac{2}{1} \rceil = 2$ and $c_2 = \lceil \frac{2+1}{2} \rceil = 2$. Both are prime numbers. For the second test case, $c_1 = c_2 = c_3 = 2$.