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.io.FileInputStream; 
import java.io.IOException; 
import java.io.InputStreamReader; 
import java.util.*; 
import java.util.StringTokenizer; 

public class Main 
{ 
    static int MAXN=201;
    static int spf[] = new int[MAXN]; 
    static int ans[]=new int[MAXN];
    static int id[]=new int[MAXN];
    static int sz[]=new int[MAXN];
    static HashSet s=new HashSet();
	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; 
		} 
	} 
    static void sieves() 
    { 
        spf[1] = 1; 
        for (int i=2; i<MAXN; i++) 
            spf[i] = i; 
        for (int i=4; i<MAXN; i+=2) 
            spf[i] = 2; 
        for (long i=3; i*i<MAXN; i++) 
        { 
            if (spf[(int)i] == i) 
            { 
                for (long j=i*i; j<MAXN; j+=i) 
                    if (spf[(int)j]==j) 
                        spf[(int)j] = (int)i; 
            } 
        } 
    } 
    static void getFactorizations(int x) 
    { 
        Vector<Integer> ret = new Vector<>(); 
        HashSet w=new HashSet();
        while (x != 1 && spf[x]!=1) 
        { 
            if(!w.contains(spf[x]) && spf[x]!=1)
            {
            w.add(spf[x]);
            ans[spf[x]]++; 
            }
            x = x / spf[x]; 
        }
    } 
	public static void main(String[] args) 
	{ 
		FastReader sc=new FastReader();
	    int T=sc.nextInt();
	    while(T-->0){
	        int N=sc.nextInt();
	        StringBuffer sb=new StringBuffer();
	        int a[]=new int[N+1];
	        PriorityQueue<Pair>pq=new PriorityQueue();
	        pq.add(new Pair(1,N));
	        int c=1;
	        while(!pq.isEmpty()){
	            Pair p=pq.poll();
	            int u=p.x;
	            int v=p.y;
    	            if((v-u+1)%2==0){
    	                int pos=(v+u-1)/2;
    	                if(a[pos]==0)
    	                a[pos]=c++;
    	                if(v-u>=1){
    	                    if(v-pos>pos-u){
    	                        pq.add(new Pair(pos+1,v));
    	                        pq.add(new Pair(u,pos-1));
    	                    }else{
    	                        pq.add(new Pair(u,pos-1));
    	                        pq.add(new Pair(pos+1,v));
    	                    }
    	                }
    	            }else{
    	                int pos=(v+u)/2;
    	                if(a[pos]==0)
    	                a[pos]=c++;
    	                if(v-u>=1){
    	                    if(v-pos>pos-u){
    	                        pq.add(new Pair(pos+1,v));
    	                        pq.add(new Pair(u,pos-1));
    	                    }else{
    	                        pq.add(new Pair(u,pos-1));
    	                        pq.add(new Pair(pos+1,v));
    	                    }
    	                }
    	            }

	           
	        }
	        for(int i=1;i<=N;i++){
	            //if(a[i]==0)a[i]=c;
	            sb.append(a[i]+" ");
	        }
	        System.out.println(sb);
	    }
	} 
	public static int root(int i)
    {
        while(i!=id[i])
        i=id[i];
        return i;
    }
    public static void union(int p,int q)
    {
        int i=root(p);
        int j=root(q);
        //System.out.println(i+" "+j);
        if(sz[i]<sz[j])
        {
            id[i]=j;
            sz[j]+=sz[i];
        }
        else
        {
            id[j]=i;
            sz[i]+=sz[j];
        }
        //max=Math.max(max,Math.max(sz[i],sz[j]));
    }
	public static void sieven(int n) 
    {
        boolean prime[] = new boolean[n+1]; 
        for(int i=0;i<n;i++) 
            prime[i] = true; 
        for(int p = 2; p*p <=n; p++) 
        { 
            if(prime[p] == true) 
            { 
                for(int i = p*2; i <= n; i += p) 
                    prime[i] = false; 
            } 
        } 
        for(int p=2; p<=n;p++)
        if(prime[p]==true)
        s.add(p);
    } 
	public static long gcd(long a,long b)
	{
	    if(b==0)
	    return a;
	    return gcd(b,a%b);
	}
	static long power(long x, long y, int p) 
    { 
        long res = 1;      
        x = x % p;  
        while (y > 0) 
        { 
            if((y & 1)==1) 
                res = (res * x) % p; 
            y = y >> 1;  
            x = (x * x) % p;  
        } 
        return res; 
    }
    static class Pair implements Comparable<Pair>
	{ 
		int x; 
		int y;
		public Pair(int x, int y) 
		{	 
			this.x = x; 
			this.y = y; 
		}	 
		public int compareTo(Pair p){
		    if(p.y-p.x<this.y-this.x)return -1;
		    if(p.y-p.x==this.y-this.x){
		        if(this.x<p.x)return-1;
		        return 1;
		    }
		    return 1;
		}
	} 
    static class Compare
	{ 
		static void compare(Pair arr[], int n) 
		{ 
			// Comparator to sort the pair according to second element 
			Arrays.sort(arr, new Comparator<Pair>() { 
				@Override public int compare(Pair p1, Pair p2) 
				{ 
					if(p1.x>p2.x)
					{
						return 1;
					}
					else if(p2.x>p1.x)
					{
						return -1;
					}
					else
					{
						return 0;
					} 
				} 
			}); 
		} 
	}
}