C. Big XOR
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given an integer $$$n$$$. Consider the array $$$a = [1, 2, \ldots, n]$$$. You may choose any elements of the array and multiply each chosen element by $$$2$$$. Each element can be doubled at most once. You may choose any subset of elements, including all of them or none of them. Denote the resulting array by $$$b$$$.

Let $$$k$$$ be the bitwise OR of all elements of the original array $$$a$$$, and let $$$m$$$ be the bitwise XOR of all elements of the resulting array $$$b$$$:

$$$$$$ k = a_1 \mathbin{|} a_2 \mathbin{|} \cdots \mathbin{|} a_n, \qquad m = b_1 \oplus b_2 \oplus \cdots \oplus b_n. $$$$$$

Choose which elements to double so that $$$m \ge 2k$$$. It can be shown that this is possible for every valid value of $$$n$$$. You do not need to minimize the number of doubled elements.

Input

The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The only line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of the array.

Additional constraints on the input:

  • the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
Output

For each test case, print $$$n$$$ integers $$$d_1, d_2, \ldots, d_n$$$. Each $$$d_i$$$ must be either $$$0$$$ or $$$1$$$: if $$$d_i = 1$$$, the element $$$a_i$$$ should be doubled; if $$$d_i = 0$$$, it should be left unchanged.

If there are multiple valid answers, output any of them.

Example
Input
5
3
6
9
5
11
Output
1 0 1
0 1 1 0 0 1
0 1 1 1 0 1 0 0 1
0 1 1 1 0
0 0 1 0 1 1 0 1 1 0 1
Note

In the first test case, $$$k = 3$$$. After doubling the chosen elements, $$$b = [2, 2, 6]$$$, and $$$m = 6$$$.

In the second test case, $$$k = 7$$$. After doubling the chosen elements, $$$b = [1, 4, 6, 4, 5, 12]$$$, and $$$m = 14$$$.