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.util.concurrent.PriorityBlockingQueue;

public class A642 {

    static class Segment implements Comparable<Segment>
    {
        int l;
        int r;
        int length;

        public Segment()
        {

        }
        public Segment(int l1, int r1)
        {
            l=l1;
            r=r1;
            length=r1-l1+1;
        }

        @Override
        public int compareTo(Segment o) {
            // TODO Auto-generated method stub
            if(o.length==this.length)
            return this.l-o.l;
            else
            return o.length-this.length;
        }

        

    }  
    public static int[] arr;
    
    public static void solve(InputReader in, PrintStream out) {
        int t= in.nextInt();

        while(t--!=0)
        {
           int n = in.nextInt();

           if(n==1)
           {
               out.println(1);
               continue;
           }
           arr = new int[n+1];
           Arrays.fill(arr,0);

           int moves = (n+1)/2;
           int i=1;
            
           PriorityQueue<Segment> q = new PriorityQueue<>(); 
           if(n%2==0)
           {
              arr[n/2]=i;
              i++;
              Segment s1 = new Segment(1,(n/2)-1);
              Segment s2 = new Segment((n/2)+1,n);
              q.add(s1);
              q.add(s2);
           }
           else{
               int idx = (n+1)/2;
              arr[idx]=i;
              i++;
              Segment s1 = new Segment(1,idx-1);
              Segment s2 = new Segment(idx+1,n);
              q.add(s1);
              q.add(s2);
           }


           while(!q.isEmpty())
           {
               Segment s = q.poll();
               
               int len = s.length;

               if(len==0 || len ==1)
               {
                   q.poll();
                   continue;
               }

               int r = s.r;
               int l = s.l;
               if(len%2==0)
            {
              int idx = (l+r-1)/2;   
              arr[idx]=i;
              i++;
              Segment s1 = new Segment(l,idx-1);
              Segment s2 = new Segment(idx+1,r);
              q.add(s1);
              q.add(s2);
           }
           else{
               int idx = (l+r)/2;
              arr[idx]=i;
              i++;
              Segment s1 = new Segment(l,idx-1);
              Segment s2 = new Segment(idx+1,r);
              q.add(s1);
              q.add(s2);
           }
           }

           for(int j=1;j<=n;j++)
           {
               if(arr[j]==0)
               {
                   arr[j]=i;
                   i++;
               }
           }

            for(int j=1;j<=n;j++)
           out.print(arr[j]+" ");

           out.println();
        }

    }

    
    
    private final static long hash(long x, long y) {
        x += offset;
        y += offset;
        return x << 32 | y;
    }
    private final static int offset = (int) 3e5;
    public static void main(String[] args) throws Exception {
      InputStream inputStream = null;
		OutputStream outputStream = null;
        InputReader in =null;
        PrintStream out = null;
		if (System.getProperty("ONLINE_JUDGE") == null) {
			inputStream = new FileInputStream("input.txt");
		    outputStream = new FileOutputStream("output.txt");
            in = new InputReader(inputStream);
            out = new PrintStream(outputStream);
            System.setOut(out);
		} else {
			inputStream = System.in;
			outputStream = System.out;
            in = new InputReader(inputStream);
            out = new PrintStream(outputStream);
		}
        solve(in, out);
        out.close();
    }
    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public Long nextLong() {
            return Long.parseLong(next());
        }

        public Double nextDouble() {
            return Double.parseDouble(next());
        }
    }
}