题目背景

克露丝卡尔酱邀请你来构造！

克露丝卡尔酱有一个长度为 $n$ 的整数数组 $a$ 。克露丝卡尔酱在想，要是能让 $a$ 的所有子数组两两配对，配对的两个子数组的和相等，那该多好啊！

克露丝卡尔酱想到了全0数组。这好像有点太简单了！于是她不允许数组中出现0了。现在你能帮她构造出满足要求的数组吗？

题目描述

给定 $n$ , 构造一个长度为 $n$ 的整数数组 $a$，满足：

• 对 $\forall i \in [1, n]$，有 $a_i \in [-10^9, 10^9]$ 且 $a_i \neq 0$。
• 取数组 $a$ 的所有子数组的和 放入 可重集 $S$ , $S$中每个元素的出现次数均为 偶数 。

若不存在构造方案，输出一个 $0$ 并换行表示无解。若有多个构造方案，输出任意一个即可。

注：子数组是指在一个数组中，选择一些连续的元素组成的新数组。子数组最少包含一个元素。

输入格式

本题有多组测试数据

第一行，输入一个正整数 $T$ $(1 \leq T \leq 40)$，表示数据组数。

接下来 $T$ 行，每行输入一个整数 $n$ $(1 \leq n \leq 1000)$, 表示需要构造的数组长度。

输出格式

输出一共 $T$ 行，每一行表示一个 $n$ 的答案。

若不存在构造方案，输出一个整数 $0$ 并换行。

否则，在一行内输出 $n$ 个空格分隔的整数并换行，表示你的构造方案。

注意你输出的构造方案需要满足 $a[i]\neq 0$。

2
6
8

0
-5 6 2 -5 3 2 -3 -5

提示

假设构造的数组是 {1,2,2,3} ，则先计算所有子数组的和：

• 长度为 1 的子数组：1, 2, 2, 3
• 长度为 2 的子数组：3, 4, 5
• 长度为 3 的子数组：5, 7
• 长度为 4 的子数组：8

将这些子数组的和放入可重集 $S$ 中，得到 $S = \{1, 2, 2, 3, 3, 4, 5, 5, 7, 8\}$。其中元素 1 出现了 1 次，元素 2 出现了 2 次，元素 3 出现了 2 次，元素 4 出现了 1 次，元素 5 出现了 2 次，元素 7 出现了 1 次，元素 8 出现了 1 次。由于元素 1、4、7、8 的出现次数为奇数，因此这个数组不满足题目的要求。