B. 交替序列
每个测试的时间限制：$2$ 秒
内存限制：$256$ 兆字节

给你一个整数 $n$。如果一个长度为 $n$ 的数组 $a$ 满足以下条件，则称它为 好数组：

• 对所有 $1 \le i < n$，有 $a_i \cdot a_{i+1} < 0$（即相邻元素的乘积为负）。
• 对所有长度至少为 $2$ 的子数组*，该子数组内所有元素的和为正†。

此外，如果一个长度为 $n$ 的好数组 $a$ 比另一个长度为 $n$ 的好数组 $b$ 更好，当且仅当
$[|a_1|, |a_2|, \dots, |a_n|]$ 在字典序‡上小于 $[|b_1|, |b_2|, \dots, |b_n|]$。
注意 $|z|$ 表示整数 $z$ 的绝对值。

请输出一个长度为 $n$ 的好数组，使得它比所有其他长度为 $n$ 的好数组都更好。

*子数组 $c$ 是数组 $d$ 的子数组，如果 $c$ 可以通过从 $d$ 的开头删除若干（可能为零或全部）元素，并从结尾删除若干（可能为零或全部）元素得到。

†整数 $x$ 是正数，如果 $x > 0$。

‡序列 $a$ 在字典序上小于序列 $b$，当且仅当以下条件之一成立：

• $a$ 是 $b$ 的一个前缀，但 $a \ne b$；
• 在 $a$ 和 $b$ 第一个不相同的位置上，$a$ 的元素小于 $b$ 的对应元素。

输入格式
第一行包含一个整数 $t$（$1 \le t \le 500$）——测试用例的数量。

每个测试用例的单行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$）——数组的长度。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

输出格式
对于每个测试用例，在新的一行输出 $n$ 个整数 $a_1, a_2, \dots, a_n$（$-10^9 \le a_i \le 10^9$），即你的数组元素。

示例输入

2
2
3

示例输出

-1 2
-1 3 -1

提示

• 在第一个测试用例中，因为 $a_1 \cdot a_2 = -2 < 0$ 且 $a_1 + a_2 = 1 > 0$，满足两个条件。并且可以证明，对应的 $b = [1, 2]$ 比其他任何长度为 $2$ 的好数组都更好。