思路

• 对每一位独立考虑：该位上 $XOR$ 为该位被置$1$的元素个数的奇偶性；$OR$ 为是否至少一个元素该位为 $1$。

• 要使 $XOR$ 与 $OR$ 在每一位都相等，必须“该位为 $1$ 的个数”要么为 $0$，要么为奇数（不能是正偶数）。

• 简单构造：

  • $n$ 为奇数：输出全部为 $1$。此时最低位出现 $n$ 次（奇数），其他位为 $0$。
  • $n$ 为偶数：输出 $n−1$ 个 $1$，最后一个为 $2$。此时最低位出现 $n−1$ 次（奇数），第二位出现 $1$ 次（奇数），其他位为 $0$。

• 值域均在 $1..1e9$ 内，复杂度 O($∑n$)。

题目内容

Tk 有一个长度为 $n$ 的数组 {$a_1,a_2,...,a_n$} 初始数组中所有元素均为 $0$ 。Tk 希望你给数组的每个元素都赋予一个正整数，使得数组满足：

• $a_1$ $xor$ $a_2$ $xor...$ $xor$ $a_n=a_1$ $or$ $a_2$ $or...$ $or$ $a_n$。

【按位异或】按位异或(xor)运算是对整数的二进制表示的每一位执行异或操作；

【按位或】按位或(or)运算是对整数的二进制表示的每一位执行或操作。

输入描述

每个测试文件均包含多组测试教据。第一行输入一个整数 $T(1≦T≦10^4)$ 代表数据组数；

随后每组测试数据描述如下：

在一行上输入一个整数 $n(1≦n≦2×10^5)$ ；

除此之外，保证所有测试数据的 $n$ 之和不超过 $2×10^5$ 。

输出描述

对于每一组测试数据，新起一行。输出 $n$ 个整数 $a_1,a_2,...,a_n(1≤a_i≤10^9)$，表示所构造的数组；可以证明一定有解。

如果存在多种可行解，可输出任意一种，系统会自动判定是否正确。

样例1

输入

2
4
1

输出

5 6 4 8
6

说明

对于第一组数据 $a_1$ $or$ $a_2$ $or...$ $or$ $a_n=15,$$a_1$ $xor$ $a_2$ $xor...$ $a_n = 15$ 满足条件。