For a positive integer $n$, a sequence of length $n$ is called a “red-brick sequence” if it satisfies the following conditions:

• Each of $1, 2, \ldots, n$ appears exactly once in the sequence.
• The sum of every pair of adjacent elements is not a perfect square.

Given an integer $n$, construct a red-brick sequence of length $n$.

Input

The first line contains an integer $T$ ($1 \le T \le 10^4$), the number of test cases.

For each test case, the only line contains an integer $n$ ($1 \le n \le 4 \times 10^6$), the required length of the red-brick sequence.

It is guaranteed that the sum of $n$ does not exceed $4 \times 10^6$. It can be proved that a solution always exists under the given constraints.

Output

Output $T$ lines, each containing the sequence to be constructed. If there are multiple answers, output any of them.

Examples

Input 1

5
1
2
3
4
5

Output 1

1
1 2
1 2 3
1 2 3 4
1 4 2 3 5

Note

For $n = 5$, if the output sequence is 1 2 3 4 5, it is a wrong answer because $4 + 5 = 9$ is a perfect square.