题目描述

Tk 有一个长度为 $n$ 的数组 $[a_1,a_2,...,a_n]$初始数组中所有元素均为 $0$ 。

Tk 希望你给数组的每个元素都赋予一个正整数，使得数组满足：

$a_1\oplus a_2\oplus ...\oplus a_n=a_1 | a_2|...|a_n$

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

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

输入描述

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

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

在一行上输入一个整数 $n(1\le n\le 2\times 10^5)$ ；

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

输出描述

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

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

样例1

输入

2
4
1

输出

5 6 4 8
6

样例解释

对于第一组数据 $a_1\oplus a_2\oplus ...\oplus a_n=a_1 | a_2|...|a_n= 15$ 满足条件。