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.*;

public class Test{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while(t>0){
           PriorityQueue<Segment> q = new 
           PriorityQueue<Segment>(5, new SegmentComparator()); 
           int n = sc.nextInt();
           int[] a = new int[n+1];
           a[0]=-1;
            int l = 1;
            int r = n;
            int mid = 0;
            Segment s = new Segment(1,n);
            q.add(s);
           for(int i=1;i<n+1;i++){
               s = q.poll();
               l = s.getL();
               r = s.getR();
            //   System.out.println("l "+l+"r "+r);
               if((r-l+1)%2 != 0){
                   a[(l+r)/2]=i;
                   mid = (l+r)/2;
               }
               else{
                   a[(l+r-1)/2]=i;
                   mid = (l+r-1)/2;
               }
               if(l==r){
                   
               }
               else if(l == mid){
                   s = new Segment(r,r);
                   q.add(s);
                //   System.out.println("r + "+r);
               }
               else{
                   if((r-l+1)%2 != 0){
                       s = new Segment(l,mid-1);
                       q.add(s);
                    //   System.out.println(s.l+" "+s.r);
                       s = new Segment(mid+1,r);
                       q.add(s);
                    //   System.out.println(s.l+" "+s.r);
                   }
                   else{
                       s = new Segment(mid+1,r);
                       q.add(s);
                    //   System.out.println(s.l+" "+s.r+" even");
                       s = new Segment(l,mid-1);
                       q.add(s);
                    //   System.out.println(s.l+" "+s.r+" even");
                   }
               }
           }
           
           for(int i=1;i<n+1;i++){
               System.out.print(a[i]+" ");
           }
           System.out.println();
           t--;
        }
    }
}

class SegmentComparator implements Comparator<Segment>{ 
              
            // Overriding compare()method of Comparator  
                        // for descending order of cgpa 
            public int compare(Segment s1, Segment s2) { 
                if (s1.length<s2.length) 
                    return 1; 
                else if (s1.length>s2.length) 
                    return -1;
                else if (s1.l>s2.l)
                    return 1;
                else if (s1.l<s2.l)
                    return -1;
                                return 0; 
                } 
        } 
  
class Segment { 
    public int l; 
    public int r; 
    public int length;
          
    // A parameterized student constructor 
    public Segment(int l, int r) { 
      
        this.l = l;
        this.r = r;
        this.length = r-l;
        
    } 
      
    public int getL() { 
        return l; 
    }  
    
    public int getR() {
        return r;
    }
    
    public int getLength() {
        return length;
    }
}