Background

The difference between this problem and the Hard Version is that this problem requires you to output a valid construction.

Problem Description

Define $\operatorname{mex}(x, y)$ as the smallest natural number that does not appear in the set $\{x, y\}$. For example, $\operatorname{mex}(1, 5) = 0$ and $\operatorname{mex}(3, 0) = 1$.

Next, we define one operation on a natural number sequence $a_1 \dots a_n$ as replacing sequence $a$ with a sequence $b_1 \dots b_{n-1}$ of length $\bm{n - 1}$, where $b_i = \operatorname{mex}(a_i, a_{i+1})$.

You need to construct a natural number sequence $a_1 \dots a_n$ of length $n$, satisfying $0 \leq a_i \leq 10^9$, and then perform $n - 1$ operations on it. Obviously, in the end the sequence $a$ will have only one number left, and you need to maximize the value of this number.

If there are multiple possible sequences, you may output any valid construction.

Input Format

This problem contains multiple test cases.

The first line contains a positive integer $T$, the number of test cases.

For each test case, there is only one line containing a positive integer $n$.

Output Format

For each test case, output one line with $n$ integers, representing the sequence $a_1 \dots a_n$ you constructed.

3
2
5
7

0 1
3 1 5 0 1
0 7 9 4 0 0 4

Hint

Sample Explanation

For $n = 2$, after applying the operation to $[0, 1]$, we will clearly get $[2]$. It can be proven that this is the maximum answer we can obtain.
Other valid outputs such as $[1, 0]$ can also work.

For $n = 5$ and $n = 7$, we cannot give you a clear answer for now.

Constraints

"This problem uses bundled tests"

Special property $\text{A}$: it is guaranteed that $n \equiv 3 \pmod 4$.

Special property $\text{B}$: it is guaranteed that $n \equiv 2 \pmod 4$.

For all testdata, it is guaranteed that $1 \leq T \leq 10^4$, $n > 1$, and $\sum n \leq 10^6$.

Translated by ChatGPT 5