Problem Statement

You are given a positive integer $N$. Output one pair of non-negative integer sequences $P=(P_1, P_2, \dots,P_N), A=(A_1, A_2, \dots,A_N)$ that satisfies all of the following conditions:

• $0 \leq P_i < 2^{30}~(1 \leq i \leq N)$
• $0 \leq A_i < 2^{30}~(1 \leq i \leq N)$
• The length of a longest strictly increasing subsequence of $(P_1~\mathrm{OR}~A_i, P_2~\mathrm{OR}~A_i, \dots, P_N~\mathrm{OR}~A_i)$ is $i$. $(1 \leq i \leq N)$
• $\mathrm{OR}$ denotes the bitwise $\mathrm{OR}$ operation.

It can be proved that under the constraints of this problem, there exists at least one pair $P, A$ that satisfies the conditions.

Solve $T$ test cases per input.

What is bitwise $\mathrm{OR}$? The bitwise $\mathrm{OR}$ of non-negative integers $A, B$, denoted $A\ \mathrm{OR}\ B$, is defined as follows: When $A\ \mathrm{OR}\ B$ is written in binary, the digit at position $2^k$ ($k \geq 0$) is $1$ if at least one of the digits at position $2^k$ in the binary representations of $A$ and $B$ is $1$, and $0$ otherwise. For example, $3\ \mathrm{OR}\ 5 = 7$ (in binary: $011\ \mathrm{OR}\ 101 = 111$).

Constraints

• $1 \leq T$
• $1 \leq N \leq 1024$
• For test cases in a single input, the sum of $N$ is at most $200000$.
• For test cases in a single input, the sum of $N^2$ is at most $1024^2$.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

Each case is given in the following format:

N

Output

Output a solution for $\mathrm{case}_1, \mathrm{case}_2, \dots, \mathrm{case}_T$ in this order.

For each case, output the answer in the following format:

P_1 P_2 \ldots P_N
A_1 A_2 \ldots A_N

If there are multiple solutions, any of them will be considered correct.