E. 环形操作
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Papy 手里有一个大小为 $$$n$$$ 的环形数组 $$$a_1, a_2, \dots, a_n$$$。刚开始的时候，数组里的每一个元素都是 $$$1$$$（即对于所有的 $$$1 \le i \le n$$$，都有 $$$a_i = 1$$$）。

环形数组的下标按照顺时针循环排列，即 $$$a_n$$$ 的下一个元素是 $$$a_1$$$，$$$a_1$$$ 的上一个元素是 $$$a_n$$$。

Papy 现在可以进行若干次操作。每次操作中，你可以选择一个下标 $$$i$$$ ($$$1 \le i \le n$$$)，并执行以下修改：

  • $$$a_{i-1} \leftarrow a_{i-1} - 1$$$
  • $$$a_i \leftarrow a_i + 2$$$
  • $$$a_{i+1} \leftarrow a_{i+1} - 1$$$

（特别地，当 $$$i=1$$$ 时，$$$i-1$$$ 对应的就是 $$$n$$$；当 $$$i=n$$$ 时，$$$i+1$$$ 对应的就是 $$$1$$$。）

Papy 希望每次调整后，数组里的每一个元素都必须保持是非负整数。这意味着，只有当位置 $$$i$$$ 的左右两个邻居都至少为 $$$1$$$ 时，你才可以对位置 $$$i$$$ 进行操作。当再也找不到任何可以合法调整的位置时，过程就会自然停止。

Papy 希望这个操作过程能尽可能多地玩几轮。请你帮帮他，设计一种能让总操作次数达到最多的方案，并输出最终停下来时数组的样子。如果有多种方案都能达到最多的操作次数，输出其中任意一种合法的最终状态即可。

Input

第一行输入一个正整数 $$$T\ (1\le T\le 10^4)$$$，表示测试组数。

接下来的 $$$T$$$ 组测试中，每组输入格式如下：

  • 第一行输入一个整数 $$$n$$$ ($$$3 \le n \le 2\times 10^5$$$)，表示环形数组的大小。

此外，数据保证所有测试组 $$$n$$$ 的总和不超过 $$$2\times 10^5$$$。

Output

对于每组测试，输出一行包含 $$$n$$$ 个用空格隔开的整数，代表在操作次数最多的前提下，最终数组各个位置的数值 $$$a_1, a_2, \dots, a_n$$$。

如果有多种合法的最终状态都能达到最大的操作次数，你只需要输出其中的任意一种最终状态即可。

Example
Input
1
3
Output
3 0 0