對於正整數 $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$ 係完全平方數。