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:


/**
 *
 * @author Harshwardhan Yadav
 */
import java.math.*;
import java.io.*;
import java.util.*;
public class Codeforces {

    /**
     * @param args the command line arguments
     */
    
    static class Valueable{
        int l,r;
        Valueable(int l,int r)
        {
            this.l=l;
            this.r=r;
        }
    }

    static class Sortbyroll implements Comparator<Valueable> 
    { 
        // Used for sorting in ascending order of 
        // roll number 
        @Override
        public int compare(Valueable a,Valueable b)
        {
            return a.l-b.l;
        }
    } 

    static int findMaxElementIndex(int ar[])
    {
        int index=0;
        int max=0;
        int n=ar.length;
        for(int i=0;i<n;i++)
        {
            if(ar[i]>max)
            {
                max=ar[i];
                index=i;
            }
        }
        return index;
    }

    static int findMaxElement(int ar[])
    {
        int max=0;
        int n=ar.length;
        for(int i=0;i<n;i++)
        {
            if(ar[i]>max)
            {
                max=ar[i];
            }
        }
        return max;
    }

    static int binarySearch(int arr[],int value,int start,int end)
    {
        int mid=(start+end)/2;
        int result;
        if(start<=end)
        {
            if(arr[mid]==value)
            {
                return mid;
            }
            else if(arr[mid]<value)
            {
                result=binarySearch(arr, value, mid+1, end);
            }
            else{
                result=binarySearch(arr, value, start, mid-1);
            }
        }
        else{
            return -1;
        }
        return result;
    }
    
    static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
 
        public FastReader() 
        { 
            br = new BufferedReader(new
                    InputStreamReader(System.in)); 
        } 
 
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
 
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
 
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
 
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
 
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        }
        
        int[] nextIntArray(int n)
        {
            int arr[]=new int[n];
            for(int i=0;i<n;i++)
            {
                arr[i]=Integer.parseInt(next());
            }
            return arr;
        }

        Integer[] nextIntegerArray(int n)
        {
            Integer arr[]=new Integer[n];
            for(Integer i=0;i<n;i++)
            {
                arr[i]=Integer.parseInt(next());
            }
            return arr;
        }

        long[] nextLongArray(int n)
        {
            long arr[]=new long[n];
            for(int i=0;i<n;i++)
            {
                arr[i]=Long.parseLong(next());
            }
            return arr;
        }

    } 
 
    static int gcd(Integer a,Integer b)
    {
        if(b==0)
            return a;
        else
            return gcd(b,a%b);
    }
 
    static boolean checkForPrime(long inputNumber)
    {
        boolean isItPrime = true;
        if(inputNumber <= 1) 
        {
            isItPrime = false;
            return isItPrime;
        }
        else
        {
            if(inputNumber%2==0 && inputNumber==2)
            {
                return true;
            }
            else if(inputNumber%2==0)
            {
                return false;
            }
            else{
                int check=(int)Math.sqrt(inputNumber);
                for (int i = 3; i<= check; i+=2) 
                {
                    if ((inputNumber % i) == 0)
                    {
                        isItPrime = false;
                        break;
                    }
                }
            }
        }
 
        return isItPrime;
    } 
    
    static SortedSet<Valueable> ts=new TreeSet<Valueable>(new Comparator<Valueable>(){
        @Override
        public int compare(Valueable a,Valueable b)
        {
            if(a.r-a.l==b.r-b.l)
            {
                return a.l-b.l;
            }
            else{
                return (-1)*((a.r-a.l)-(b.r-b.l));
            }
        }
    }
    );
    static Valueable[] queue=new Valueable[200000];
    static int F=-1,R=-1;
    
    static void solve(int arr[],int l,int r,int count)
    {
        if(l<=r)
        {
            if((r-l+1)%2!=0)
            {
                arr[(l+r)/2]=count;
                if(l<=(l+r)/2-1)
                    ts.add(new Valueable(l,(l+r)/2-1));
                if((l+r)/2+1<=r)
                    ts.add(new Valueable((l+r)/2+1,r));
            }
            else{
                arr[(l+r-1)/2]=count;
                if((l+r-1)/2+1<=r)
                    ts.add(new Valueable((l+r-1)/2+1,r));
                if(l<=(l+r-1)/2-1)
                    ts.add(new Valueable(l,(l+r-1)/2-1));
            }
        }
    }
    
    static void enqueue(int l,int r)
    {
        R++;
        queue[R]=new Valueable(l,r);
        if(F==-1)
            F++;
    }
    static Valueable dequeue()
    {
        Valueable ob=queue[F];
        if(F==R)
            F=R=-1;
        else
            F++;
        return ob;
    }
    
    public static void main(String[] args) throws UnsupportedEncodingException, IOException {
        // TODO code application logic here
        FastReader sc=new FastReader();
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(new FileOutputStream(java.io.FileDescriptor.out), "ASCII"), 512);
        int t=sc.nextInt();
        for(int test=0;test<t;test++)
        {
            int n=sc.nextInt();
            int[] arr=new int[n];
            int count=1,l=0,r=n-1;
            solve(arr,l,r,count);
            while(!ts.isEmpty())
            {
                count++;
                Valueable ob=ts.first();
                ts.remove(ob);
                solve(arr,ob.l,ob.r,count);
            }
            for(int i=0;i<n;i++)
            {
                out.write(arr[i]+" ");
            }
            out.write("\n");
            out.flush();
        }
        out.close();
    }
    
}