「LAOI-4」Mex Tower (Easy ver.)

题目背景

**本题与 Hard Version 的区别为本题需给出一个合法的方案。**

题目描述

定义 $\operatorname{mex}(x, y)$ 表示在集合 $\{x, y\}$ 中最小的未出现的 **自然数**。例如,$\operatorname{mex}(1, 5) = 0$,$\operatorname{mex}(3, 0) = 1$。 继而,我们定义对自然数序列 $a_1\dots a_n$ 的一次操作,是将序列 $a$ 替换为 **长度为 $\bm{n - 1}$ 的** 序列 $b_1\dots b_{n-1}$,其中 $b_i = \operatorname{mex}(a_i, a_{i+1})$。 你需要构造一个长度为 $n$ 的自然数序列 $a_1\dots a_n$,满足 $0 \leq a_i \leq 10^9$;然后对它进行 $n - 1$ 次操作。显然最终序列 $a$ 只会剩下一个数,你需要最大化这个数的值。 如果有多种可能的数列,可以输出任何一种合法方案。

输入输出格式

输入格式


**本题有多组数据。** 第一行一个正整数 $T$,表示数据组数。 对于每组数据,仅一行,一个正整数 $n$。

输出格式


对于每组数据,输出一行 $n$ 个整数,表示你构造的 $a_1\dots a_n$。

输入输出样例

输入样例 #1

3
2
5
7

输出样例 #1

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

说明

### 样例解释 对于 $n = 2$,我们对 $[0, 1]$ 进行操作后显然会得到 $[2]$。可以证明,这是我们能得到的最大的答案。 其它合法的输出如 $[1, 0]$ 等也可以通过。 对于 $n = 5$ 和 $n = 7$,暂时不能给你一个明确的答复。 ### 数据规模与约定 **「本题采用捆绑测试」** | $\text{Subtask}$ | $\sum n \le$| 特殊性质 | 总分值 | | :--------------: | :-----: |:-----: | :--------: | | $1$ | $10$ | 无| $5$ | $2$ | $10^5$ | $\text{A}$ | $15$ | | $3$ | $10^5$ | $\text{B}$ | $15$ | | $4$ | $50$ | $n\le 25$ | $10$ | | $5$ | $10^3$ | 无 | $20$ | | $6$ | $10^6$ | 无 | $35$ | 特殊性质 $\text{A}$:保证 $n\equiv 3\pmod 4$。 特殊性质 $\text{B}$:保证 $n\equiv 2\pmod 4$。 对于所有数据,保证 $1 \leq T \leq 10^4$,$n > 1$,$\sum n \leq 10^6$。