#P1722G. Even-Odd XOR

    ID: 7883 Type: RemoteJudge 1000ms 256MiB Tried: 0 Accepted: 0 Difficulty: (None) Uploaded By: Tags>bitmasksconstructive algorithmsgreedy*1500

Even-Odd XOR

No submission language available for this problem.

Description

Given an integer nn, find any array aa of nn distinct nonnegative integers less than 2312^{31} such that the bitwise XOR of the elements on odd indices equals the bitwise XOR of the elements on even indices.

The first line of the input contains an integer tt (1t6291 \leq t \leq 629) — the number of test cases.

Then tt lines follow, each containing a single integer nn (3n2105)(3 \leq n \leq 2\cdot10^5) — the length of the array.

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

For each test case, output one line containing nn distinct integers that satisfy the conditions.

If there are multiple answers, you can output any of them.

Input

The first line of the input contains an integer tt (1t6291 \leq t \leq 629) — the number of test cases.

Then tt lines follow, each containing a single integer nn (3n2105)(3 \leq n \leq 2\cdot10^5) — the length of the array.

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

Output

For each test case, output one line containing nn distinct integers that satisfy the conditions.

If there are multiple answers, you can output any of them.

Sample Input 1

7
8
3
4
5
6
7
9

Sample Output 1

4 2 1 5 0 6 7 3
2 1 3
2 1 3 0
2 0 4 5 3
4 1 2 12 3 8
1 2 3 4 5 6 7
8 2 3 7 4 0 5 6 9

Note

In the first test case the XOR on odd indices is 4107=24 \oplus 1 \oplus 0 \oplus 7 = 2 and the XOR on even indices is 2563=22 \oplus 5 \oplus 6 \oplus 3= 2.