对于正整数 $n$，一个长度为 $n$ 的序列被称为“红砖序列”，如果它满足以下条件：

• $1, 2, \ldots, n$ 中的每个数在序列中恰好出现一次。
• 每一对相邻元素的和都不是完全平方数。

给定一个整数 $n$，请构造一个长度为 $n$ 的红砖序列。

输入格式

第一行包含一个整数 $T$（$1 \le T \le 10^4$），表示测试数据的组数。

对于每组测试数据，唯一的一行包含一个整数 $n$（$1 \le n \le 4 \times 10^6$），表示所求红砖序列的长度。

保证所有测试数据中 $n$ 的总和不超过 $4 \times 10^6$。可以证明在给定数据范围下解总是存在的。

输出格式

输出 $T$ 行，每行包含所构造的序列。如果有多种合法方案，输出任意一种即可。

样例

输入格式 1

5
1
2
3
4
5

输出格式 1

1
1 2
1 2 3
1 2 3 4
1 4 2 3 5

说明

对于 $n = 5$，如果输出序列为 1 2 3 4 5，则是错误的，因为 $4 + 5 = 9$ 是完全平方数。