Sub Sequence

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

Description

Recently, YCC is studying sequence problems. And he is struggling with it!!!= =
For such an ACMer like you, it is commonly believed that you must know the Longest Increasing Subsequence problem. Now Let’s define some useful functions and symbols:
Let U(A) be the length of the longest increasing subsequence of the original sequence A;
Let D(A) be the length of the longest decreasing subsequence of the original sequence A;
Let H(A) be the maximum value of U(A) and D(A), that is H(A) = max{U(A), D(A)}.
H(A)!!! Ah... Zauber anzahl, ist es nicht?
Now YCC wants to study the attributes of all the permutations of integer numbers from 1 to N. He wants to get such permutation P having minimum H(P). If more than one permutation satisfies the condition, you should give the lexicographically smallest one.

Input

The first line contains an integer T which indicates the number of test cases.
The following T lines each contain an integer N (1 ≤ N ≤ 100000).

Output

For each case, output N space separated integers in one line, which denote the permutation expected.

Sample Input

3 1 2 3

Sample Output

1 1 2 1 3 2

Hint

zhuyuanchen520

Source

2012 Multi-University Training Contest 8

提交代码