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.util.*;
import java.lang.*;
import java.io.*;

public class test
{
	public static void main (String[] args) throws java.lang.Exception
	{
		inputs in=new inputs (System.in);
		int t = in.nextInt();
		while(--t>=0)
		{
			int n=in.nextInt();
			
			int arr[]=new int [n];
			
			PriorityQueue<Range> pq = new PriorityQueue<Range>(5, new RangeComparator()); 
			Range objf = new Range(0,n-1);
			pq.add(objf);
			int c = 1;
			while(!pq.isEmpty())
			{
				Range obj = pq.poll();
				if (obj.st==obj.en)
				{
					arr[obj.st] = c;
					c++;
				}
				else
				{
					int ind = (obj.st+obj.en)/2;
					arr[ind] = c;
					c++;
					if (ind-1>=obj.st)
					{
						Range obj1 = new Range(obj.st, ind-1);
						pq.add(obj1);
					}

					if (ind+1<=obj.en)
					{
						Range obj2 = new Range(ind+1, obj.en);
						pq.add(obj2);
					}
				}
				
			}

			for(int i=0;i<n;i++)
			System.out.print(arr[i]+" ");
			System.out.println();

		}
		
	}
}

class inputs
{
    public BufferedReader reader;
    public StringTokenizer token;

    inputs(InputStream str)
    {
        reader=new BufferedReader(new InputStreamReader(str));
        token=null;
    }

    int nextInt()
    {
        while(token==null||!token.hasMoreTokens())
        {
            try { token=new StringTokenizer(reader.readLine());   }
            catch(IOException e){  throw new RuntimeException(e); }
        }
        return Integer.parseInt(token.nextToken());
    }

    long nextLong()
    {
        while(token==null||!token.hasMoreTokens())
        {
            try { token=new StringTokenizer(reader.readLine());   }
            catch(IOException e){  throw new RuntimeException(e); }
        }
        return Long.parseLong(token.nextToken());
    }

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

}

 
class RangeComparator implements Comparator<Range>{ 
            public int compare(Range s1, Range s2) { 
                if ((s1.en-s1.st) < (s2.en-s2.st)) 
                    return 1; 
                else if ((s1.en-s1.st) > (s2.en-s2.st)) 
                    return -1; 
				else{
					if (s1.st<s2.st)
					return -1;
					else
					return 1;
				}
				// return 0;
                } 
        } 
  
class Range { 
    public int st; 
    public int en; 
    public Range(int st, int en) { 
      
        this.st = st; 
        this.en = en;
    }  
}