You are given an integer $n$. Call an array $a$ of length $n$ good if:

• For all $1 \le i \lt n$, $a_i \cdot a_{i+1} \lt 0$ (i.e., the product of adjacent elements is negative).
• For all subarrays$^{\text{∗}}$ with length at least $2$, the sum of all elements in the subarray is positive$^{\text{†}}$.

Additionally, we say a good array $a$ of length $n$ is better than another good array $b$ of length $n$ if $[|a_1|, |a_2|, \ldots, |a_n|]$ is lexicographically smaller$^{\text{‡}}$ than $[|b_1|, |b_2|, \ldots, |b_n|]$. Note that $|z|$ denotes the absolute value of integer $z$.

Output a good array of length $n$ such that it is better than every other good array of length $n$.

$^{\text{∗}}$An array $c$ is a subarray of an array $d$ if $c$ can be obtained from $d$ by the deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

$^{\text{†}}$An integer $x$ is positive if $x \gt 0$.

$^{\text{‡}}$A sequence $a$ is lexicographically smaller than a sequence $b$ if and only if one of the following holds:

• $a$ is a prefix of $b$, but $a \ne b$; or
• in the first position where $a$ and $b$ differ, the sequence $a$ has a smaller element than the corresponding element in $b$.

Input

The first line contains an integer $t$ ($1 \leq t \leq 500$) — the number of test cases.

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

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, output $n$ integers $a_1, a_2, \dots, a_n$ ($-10^9 \leq a_i \leq 10^9$), the elements of your array on a new line.

Note

In the first test case, because $a_1 \cdot a_2 = -2 \lt 0$ and $a_1 + a_2 = 1 \gt 0$, it satisfies the two constraints. In addition, it can be shown that the corresponding $b = [1, 2]$ is better than any other good array of length $2$.

Samples

2
2
3

-1 2
-1 3 -1