Background

Kruskal-chan invites you to construct one!

Kruskal-chan has an integer array $a$ of length $n$. She is thinking: how nice it would be if all subarrays of $a$ could be paired up, and the two subarrays in each pair have equal sums!

Kruskal-chan thought of the all-zero array. That seems a bit too easy! So she does not allow zeros in the array anymore. Can you help her construct an array that satisfies the requirements?

Problem Description

Given $n$, construct an integer array $a$ of length $n$ such that:

• For $\forall i \in [1, n]$, $a_i \in [-10^9, 10^9]$ and $a_i \neq 0$.
• Put the sums of all subarrays of array $a$ into a multiset $S$. The number of occurrences of every element in $S$ must be even.

If no construction exists, output $0$ followed by a newline to indicate there is no solution. If there are multiple constructions, output any one of them.

Note: A subarray means selecting some consecutive elements in an array to form a new array. A subarray contains at least one element.

Input Format

This problem has multiple test cases.

The first line contains a positive integer $T$ $(1 \leq T \leq 40)$, the number of test cases.

The next $T$ lines each contain an integer $n$ $(1 \leq n \leq 1000)$, the length of the array to construct.

Output Format

Output a total of $T$ lines, each line giving an answer for one $n$.

If no construction exists, output an integer $0$ and a newline.

Otherwise, output $n$ integers separated by spaces on one line and end with a newline, representing your construction.

Note that your construction must satisfy $a[i] \neq 0$.

2
6
8

0
-5 6 2 -5 3 2 -3 -5

Hint

Suppose the constructed array is {1,2,2,3}. First compute 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

Put these subarray sums into multiset $S$,得到 $S = \{1, 2, 2, 3, 3, 4, 5, 5, 7, 8\}$. Element 1 appears 1 time, element 2 appears 2 times, element 3 appears 2 times, element 4 appears 1 time, element 5 appears 2 times, element 7 appears 1 time, and element 8 appears 1 time. Since the occurrence counts of elements 1, 4, 7, and 8 are odd, this array does not satisfy the requirements.

Translated by ChatGPT 5