Kruskal-chan invites you to construct an array!
Kruskal-chan has an integer array $a$ of length $n$. She wonders, wouldn't it be great if all subarrays of $a$ could be paired up such that the sums of the two subarrays in each pair are equal?
Kruskal-chan thought of an array of all zeros. That seems a bit too simple! So, she does not allow any $0$s in the array. Now, can you help her construct an array that satisfies the requirements?
Given $n$, construct an integer array $a$ of length $n$ such that: - For all $i \in [1, n]$, $a_i \in [-10^9, 10^9]$ and $a_i \neq 0$. - The sums of all subarrays of $a$ are placed into a multiset $S$, where the number of occurrences of each element in $S$ is even.
If no such construction exists, output a $0$ followed by a newline to indicate no solution. If there are multiple solutions, you may output any one of them.
Note: A subarray is a new array formed by choosing some contiguous elements from an array. A subarray must contain at least one element.
Input
The problem contains multiple test cases.
The first line contains a positive integer $T$ ($1 \le T \le 40$), representing the number of test cases.
For each of the next $T$ lines, input an integer $n$ ($1 \le n \le 1000$), representing the length of the array to be constructed.
Output
Output a total of $T$ lines, each representing the answer for $n$.
If no construction exists, output a single integer $0$ followed by a newline.
Otherwise, output $n$ space-separated integers on a single line, representing your construction.
Note that your constructed array must satisfy $a_i \neq 0$.
Examples
Input 1
2 6 8
Output 1
0 -5 6 2 -5 3 2 -3 -5
Note
Suppose the constructed array is $\{1, 2, 2, 3\}$. First, calculate the sums of all subarrays: - Subarrays of length 1: $1, 2, 2, 3$ - Subarrays of length 2: $3, 4, 5$ - Subarrays of length 3: $5, 7$ - Subarrays of length 4: $8$
Putting these subarray sums into a multiset $S$, we get $S = \{1, 2, 2, 3, 3, 4, 5, 5, 7, 8\}$. Here, the element $1$ appears $1$ time, $2$ appears $2$ times, $3$ appears $2$ times, $4$ appears $1$ time, $5$ appears $2$ times, $7$ appears $1$ time, and $8$ appears $1$ time. Since the occurrences of $1, 4, 7, 8$ are odd, this array does not satisfy the problem requirements.