Problem: You are given an array a of length n consisting of zeros. You perform n actions with this array: during the i-th action, the following sequence of operations appears:

  1. Choose the maximum by length subarray (continuous subsegment) consisting only of zeros, among all such segments choose the leftmost one; 
  2. Let this segment be [l; r]. If r-l+1 is odd (not divisible by 2) then assign (set) a[(l+r)/(2)] := i (where i is the number of the current action), otherwise (if r-l+1 is even) assign (set) a[(l+r-1)/(2)] := i. 



Consider the array a of length 5 (initially a=[0, 0, 0, 0, 0]). Then it changes as follows:

  1. Firstly, we choose the segment [1; 5] and assign a[3] := 1, so a becomes [0, 0, 1, 0, 0]; 
  2. then we choose the segment [1; 2] and assign a[1] := 2, so a becomes [2, 0, 1, 0, 0]; 
  3. then we choose the segment [4; 5] and assign a[4] := 3, so a becomes [2, 0, 1, 3, 0]; 
  4. then we choose the segment [2; 2] and assign a[2] := 4, so a becomes [2, 4, 1, 3, 0]; 
  5. and at last we choose the segment [5; 5] and assign a[5] := 5, so a becomes [2, 4, 1, 3, 5]. 



Your task is to find the array a of length n after performing all n actions. Note that the answer exists and unique.

You have to answer t independent test cases.

Input

The first line of the input contains one integer t (1 ≤ t ≤ 10^4) — the number of test cases. Then t test cases follow.

The only line of the test case contains one integer n (1 ≤ n ≤ 2 ⋅ 10^5) — the length of a.

It is guaranteed that the sum of n over all test cases does not exceed 2 ⋅ 10^5 (∑ n ≤ 2 ⋅ 10^5).

Output

For each test case, print the answer — the array a of length n after performing n actions described in the problem statement. Note that the answer exists and unique.

Example

Input


6
1
2
3
4
5
6


Output


1 
1 2 
2 1 3 
3 1 2 4 
2 4 1 3 5 
3 4 1 5 2 6 

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;
import java.awt.*;
public class D
{
    BufferedReader in;
    PrintWriter ob;
    StringTokenizer st;

    public static void main(String[] args) throws IOException {
        new D().run();
    }
    void run() throws IOException {
        in=new BufferedReader(new InputStreamReader(System.in));
        ob=new PrintWriter(System.out);
        int t = ni();
        while(t-->0)
            solve();
        ob.flush();
    }

    void solve() throws IOException {
        int n = ni();
        PriorityQueue<Point> pq = new PriorityQueue(new Comparator<Point>(){
            public int compare(Point x , Point y) {
                if( x.x == y.x )
                    return Integer.compare(x.y , y.y);
                else
                    return Integer.compare(y.x , x.x);
            }
        });

        int ans[] = new int[n+1];
        int c = 1;
        pq.offer(get(n,0));
        while(pq.size() != n+1) {
            Point poll = pq.poll();
            int len = poll.x;
            int start = poll.y;
            ans[start+(len-1)/2] = c++;

            pq.offer(get((len-1)/2, start));
            pq.offer(get(len/2, start+(len-1)/2 +1));
        }

        for(int i=0 ; i<n ; i++)
            ob.print(ans[i]+" ");
        ob.println();
    }

    private Point get( int x , int y ) {
        return new Point(x,y);
    }
 
    String ns() throws IOException {
        return nextToken();
    }
    long nl() throws IOException {
        return Long.parseLong(nextToken());
    }
    int ni() throws IOException {
        return Integer.parseInt(nextToken());
    }
    double nd() throws IOException {
        return Double.parseDouble(nextToken());
    } 
    String nextToken() throws IOException {
        if(st==null || !st.hasMoreTokens())
            st=new StringTokenizer(in.readLine());
        return st.nextToken();
    }
    int[] nia(int start,int b) throws IOException {
        int a[]=new int[b];
        for(int i=start;i<b;i++)
            a[i]=ni();
        return a;
    }
    long[] nla(int start,int n) throws IOException {
        long a[]=new long[n];
        for (int i=start; i<n ;i++ ) {
            a[i]=nl();
        }
        return a;
    }
    
    public void tr(Object... o) {
     System.out.println(Arrays.deepToString(o));
    }
}