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:
// package com.company;
import java.util.*;
import java.lang.*;
import java.io.*;
//****Use Integer Wrapper Class for Arrays.sort()****
public class CZ4 {
    static PrintWriter out=new PrintWriter(new OutputStreamWriter(System.out));
    public static void main(String[] Args){
        FastReader scan=new FastReader();
        int t=1;
        t=scan.nextInt();
        while(t-->0){
            int n=scan.nextInt();
            int[] arr=new int[n];
            int l=0;
            int r=n-1;
            int red=1;
            Queue<pair> q=new PriorityQueue<>(n,new mc());
            (q).add(new pair(l,r));
            while(red<=n){
                pair cur=q.remove();
                l=cur.x;
                r=cur.y;
                if((r-l+1)%2==0){
                    int pi=(r+l-1)/2;
                    arr[pi]=red;
                    if(r>=pi+1){
                        (q).add(new pair(pi+1,r));
                    }
                    if(l<=pi-1){
                        (q).add(new pair(l,pi-1));
                    }
                }else{
                    int pi=(r+l)/2;
                    arr[pi]=red;
                    if(l<=pi-1){
                        (q).add(new pair(l,pi-1));
                    }
                    if(r>=pi+1){
                        (q).add(new pair(pi+1,r));
                    }
                }
                red++;
            }
            for(int i=0;i<n;i++){
                out.print(arr[i]+" ");
            }
            out.println();
        }
        out.flush();
        out.close();
    }
    static class mc implements Comparator<pair>{
        @Override
        public int compare(pair o1, pair o2) {
            int x1=o1.x;
            int y1=o1.y;
            int x2=o2.x;
            int y2=o2.y;
            int l1=y1-x1+1;
            int l2=y2-x2+1;
            if(l1!=l2){
                return (l2-l1);
            }else{
                return x1-x2;
            }
        }
    }
    static class pair{
        int x;
        int y;
        pair(int x,int y){
            this.x=x;
            this.y=y;
        }
    }
    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;
        }
    }

}