给你一个整数$$$n$$$。调用长度为 $$$n$$$ 的数组 $$$a$$$ 好 如果:
- 对于所有 $$$1 \le i \lt n$$$,$$$a_i \cdot a_{i+1} \lt 0$$$ (即相邻元素的乘积为负)。
- 对于长度至少为$$$2$$$的所有子数组$$$^{\text{∗}}$$$,子数组中所有元素的总和为正$$$^{\text{†}}$$$。
另外,我们说一个长度为 $$$n$$$ 的好数组 $$$a$$$ 是 更好 比另一个长度为 $$$n$$$ 的好的数组 $$$b$$$ 如果 $$$[|a_1|, |a_2|, \ldots, |a_n|]$$$ 按字典顺序小于 $$$[|b_1|, |b_2|, \ldots, |b_n|]$$$ $$$^{\text{‡}}$$$。注意$$$|z|$$$表示整数$$$z$$$的绝对值。
输出一个长度为 $$$n$$$ 的良好数组,使其优于长度为 $$$n$$$ 的所有其他良好数组。
$$$^{\text{*}}$$$数组 $$$c$$$ 是数组 $$$d$$$ 的子数组,如果 $$$c$$$ 可以通过从 $$$d$$$ 删除开头的几个(可能是零个或全部)元素和从末尾删除几个(可能是零个或全部)元素来获得。
$$$^{\text{†}}$$$如果 $$$x \gt 0$$$,则整数 $$$x$$$ 为正。
$$$^{\text{‡}}$$$当且仅当满足以下条件之一时,序列 $$$a$$$ 按字典顺序小于序列 $$$b$$$:
- $$$a$$$ 是 $$$b$$$ 的前缀,但 $$$a \ne b$$$;或
- 在 $$$a$$$ 和 $$$b$$$ 不同的第一个位置,序列 $$$a$$$ 的元素比 $$$b$$$ 中的相应元素小。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 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 \leq a_i \leq 10^9$$$),即新行上的数组元素。
示例
输入复制
223
输出复制
-1 2 -1 3 -1
注意
在第一个测试用例中,因为 $$$a_1 \cdot a_2 = -2 \lt 0$$$ 和 $$$a_1 + a_2 = 1 \gt 0$$$,它满足两个约束。另外可以证明对应的$$$b = [1, 2]$$$为 更好 比任何其他 好 长度为 $$$2$$$ 的数组。