正の整数 $n$ に対し、長さ $n$ の数列が以下の条件を満たすとき、それを「赤レンガ数列」と呼びます：

• $1, 2, \ldots, n$ のそれぞれが数列にちょうど $1$ 回ずつ現れる。
• 隣接する任意の $2$ 要素の和が平方数でない。

整数 $n$ が与えられます。長さ $n$ の赤レンガ数列を $1$ つ構築してください。

入力

最初の行には、テストケースの個数を表す整数 $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$ が平方数であるため不正解となります。