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.math.*;
import java.util.*;
public class ConstructingTheArrayBruteForce {  
	public static void main(String[] args) { 
		/*Keep track of leftmost start point of sub-array of length x
		 * OR
		 * Keep track of indices that are start points of sub-arrays of length x
		 * Binary search for lengths that exist every time (optimizing for larger)
		 * Then check the number of sub-arrays of that length and take the one
		 * That is leftmost. 
		 * */
		FastScanner I = new FastScanner(); //Input
		OutPut O = new OutPut(); //Output
		int T = I.nextInt();
		StringBuilder ans = new StringBuilder();
		while (T-->0) {
			int N = I.nextInt();
			int[] a = new int[N+1];
			PriorityQueue<Lit> segs = new PriorityQueue<Lit>();
			segs.add(new Lit(1,N));
			int num = 1;
			while (num<=N) {
				Lit prev = segs.poll();
				int start = prev.start;
				int end = prev.end;
				int mid = (start+end)/2;
				a[mid]=num;
				if (mid-start>0) segs.add(new Lit(start,mid-1)); //Left sub-array
				//Removing plus one since middle element is gone now
				if (end-mid>0) segs.add(new Lit(mid+1,end));
				num++;
			}
			for (int i = 1; i <=N; i++) ans.append(a[i]+" ");
			ans.append("\n");
		}
		O.pln(ans);
	}
	static class Lit implements Comparable<Lit>{ //WOW! (Make this static by the way)
		int start;
		int end;
		public Lit(int start,int end) { //Constructor before override 
			this.start=start;
			this.end=end; //Making the numbers called in the main code loop local to this
			//comparable class (INHERITANCE)
			//LIT is it's own class now (same as double, long, etc.)
		}
		@Override
		public int compareTo(Lit lit) { //This is built in
			//A comparable interface's purpose is to compare
			//Use this in place of Integer.compare()
			//Integer.compare(x,y):=
			//If x<y ---> Returns a negative value
			//If x==y --> Returns 0
			//If x>y --> Returns a positive value
			if (this.end-this.start+1==lit.end-lit.start+1) {
				if (this.start<lit.start) return -420; //NEGATIVE means UPDATE the QUEUE
				else if (this.start>lit.start) return 60; //POSITIVE means stay constant
				return 0; //ZERO means there's a tie (beyond scope of this question though)
			}else {
				if (this.end-this.start+1>lit.end-lit.start+1) return -420;
				else return 69; //If the new segment is better than current best, replace it
				//Computer takes this message through negative value
			}
		}
	}
	public static long min(long a, long b) {return Math.min(a,b);}
	public static long max(long a, long b) {return Math.max(a,b);}
	public static int min(int a, int b) {return Math.min(a,b);}
	public static int max(int a, int b) {return Math.max(a,b);}
	public static long abs(long x, long y) {return Math.abs(x-y);}
	public static long ceil(long num, long den) {long ans = num/den; if (num%den!=0) 
	ans++; return ans;}
	public static long GCD(long a, long b) {
		if (a==0||b==0) return Math.max(a,b);
		return GCD(Math.min(a, b),Math.max(a, b)%Math.min(a, b));
	}
	public static long FastExp(long base, long exp, long mod) {
		long ans=1;
		while (exp>0) {
			if (exp%2==1) ans*=base;
			exp/=2;
			base*=base;
			base%=mod;
			ans%=mod;
		}
		return ans;
	}
	public static long ModInv(long num,long mod) {return FastExp(num,mod-2,mod);}
	public static int pop(long x) { //Returns number of bits within a number
		int cnt = 0;
		while (x>0) {
			if (x%2==1) cnt++;
			x/=2;
		}
		return cnt;
	}
	static class FastScanner {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer("");
		String next() {
			while (!st.hasMoreTokens())
				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());}
	}
	static class OutPut{
		PrintWriter w = new PrintWriter(System.out);
		void pln(double x) {w.println(x);w.flush();}
		void pln(boolean x) {w.println(x);w.flush();}
		void pln(int x) {w.println(x);w.flush();}
		void pln(long x) {w.println(x);w.flush();}
		void pln(String x) {w.println(x);w.flush();}
		void pln(char x) {w.println(x);w.flush();}
		void pln(StringBuilder x) {w.println(x);w.flush();}
		void pln(BigInteger x) {w.println(x);w.flush();}
		void p(int x) {w.print(x);w.flush();}
		void p(long x) {w.print(x);w.flush();}
		void p(String x) {w.print(x);w.flush();}
		void p(char x) {w.print(x);w.flush();}
		void p(StringBuilder x) {w.print(x);w.flush();}
		void p(BigInteger x) {w.print(x);w.flush();}
		void p(double x) {w.print(x);w.flush();}
		void p(boolean x) {w.print(x);w.flush();}
	}
}