#CF2117B. 收缩

收缩

B. 收缩
每个测试点时间限制:22
内存限制:256256 兆字节

对于一个长度为 mm 的数组 aa,定义收缩操作如下:

  • 选择一个下标 ii2im12 \le i \le m-1),使得 ai>ai1a_i > a_{i-1}ai>ai+1a_i > a_{i+1}
  • 删除 aia_i

定义一个排列 pp得分为:在 pp 上最多能执行多少次收缩操作。

Yousef 给你一个整数 nn。请构造一个长度为 nn 的排列 pp,使其得分最大。如果有多个答案,输出任意一个即可。

*排列是长度为 nn 的数组,包含 11nnnn 个不同的整数,顺序任意。例如,[2,3,1,5,4][2,3,1,5,4] 是一个排列,但 [1,2,2][1,2,2] 不是(22 出现两次),[1,3,4][1,3,4] 也不是(n=3n=3 但数组中有 44)。


输入格式

第一行输入一个整数 tt1t1031 \le t \le 10^3),表示测试用例的数量。

每个测试用例包含一个整数 nn3n21053 \le n \le 2 \cdot 10^5),表示排列的长度。

保证所有测试用例的 nn 之和不超过 21052 \cdot 10^5


输出格式

对于每个测试用例,输出任意一个排列 p1,p2,,pnp_1, p_2, \dots, p_n,使得收缩操作的次数最大。


示例

输入:

2
3
6

输出(可能不唯一):

1 3 2
2 3 6 4 5 1

样例解释

第一个测试用例n=3n=3):

  • 选择 p=[1,3,2]p = [1,3,2]
  • 选择下标 22,删除 p2p_2,数组变为 [1,2][1,2]
  • 可以证明最大操作次数为 11
    另一个有效答案是 [2,3,1][2,3,1]

第二个测试用例n=6n=6):

  • 选择 p=[2,3,6,4,5,1]p = [2,3,6,4,5,1]
  • 选择下标 55(值为 55),删除后得到 [2,3,6,4,1][2,3,6,4,1]
  • 选择下标 33(值为 66),删除后得到 [2,3,4,1][2,3,4,1]
  • 选择下标 33(值为 44),删除后得到 [2,3,1][2,3,1]
  • 选择下标 22(值为 33),删除后得到 [2,1][2,1]
  • 最大操作次数为 44。任意得分为 44 的排列都是有效答案。