dash正在做他的小学作业：

找到一个长度为 $2n$ 的非零整数序列 $a$，使其满足

$$(a_1 \times a_2) + (a_3 \times a_4) + \dots + (a_{2n-1} \times a_{2n}) = \\ a_1 \times (a_2 + a_3) \times (a_4 + a_5) \times \dots \times (a_{2n-2} + a_{2n-1}) \times a_{2n} \neq 0 $$

更简化的形式为：

$$\sum_{i=1}^{n} a_{2i-1} \cdot a_{2i} = a_1 \cdot a_{2n} \cdot \prod_{i=2}^{n} (a_{2i-2} + a_{2i-1}) \neq 0 $$

dash当然知道如何解决这个问题，但他想考考你。你能解决这个问题吗？

输入格式

每个测试包含多个测试用例。第一行包含一个整数 $t \ (1 ≤ t ≤ 10^5)$，表示测试用例的数量。

对于每个测试用例，只有一行包含一个整数 $n \ (2 ≤ n ≤ 10^5)$。

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

输出格式

对于每个测试用例，输出一行包含 $2n$ 个整数 $a_1, a_2, \dots, a_{2n}$，满足条件 $(1 ≤ |a_i| ≤ 10^{10})$。

可以证明答案总是存在。

如果有多个可能的答案，输出其中任何一个即可。

示例

3 
2 
3 
4

1 -3 -3 1 
1 -10 6 6 -10 1 
1 -15 10 -1 -1 10 -15 1