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$$$.

Alternating Series

Examples