Description

不知道为什么，ycc 总是和数列过不去!= =

相信最长上升子序列（LIS）问题大家都会。则对于一个序列 A ，记 U(A) 为 A 数列的最长上升子序列的长度，D(A) 为 A 数列的最长下降子序列的长度。而这两个值的最大值，即max{U(A), D(A)} ，似乎是一个很神奇的数，记为 H(A) 。

现在 ycc 要研究 1..N 排列的子序列性质，现在要求 1..N 的某个排列 B ，使得 H(B) 最小。若有多个排列满足条件，则输出字典序最小的那个。

Input

第一行一个数 T ，表示有 T 组数据。接下来每行一个整数 N ，1 <= N <= 100000 。

Output

对于每个 N ，输出要求的序列，占一行，用一个空格分隔两个相邻的数，行首和行末不能出现多余空格。

Sample

Input

3
1
2
3

Output

1
1 2
1 3 2