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:
/*
Some say the world will end in fire,
Some say in ice.
From what I've tasted of desire
I hold with those who favor fire.
But if it had to perish twice,
I think I know enough of hate
To say that for destruction ice
Is also great
And would suffice.
*/
import java.io.*;
import java.util.*;
 
public final class Main{
    
    static class DSU{
        int[] parent;
        int[] size;
        DSU(int n){
            parent = new int[n + 1];
            size = new int[n + 1];
            for(int i = 0; i <= n; i++){
                parent[i] = i;
                size[i] = 1;
            }
        }
        int getRoot(int i){
            while(i != parent[i]){
                parent[i] = parent[parent[i]];
                i = parent[i];
            }
            return i;
        }
        boolean find(int i, int j){
            return (getRoot(i) == getRoot(j)) ? true : false;
        }
        void union(int i, int j){
            if(find(i, j))  return;
            int rooti = getRoot(i);
            int rootj = getRoot(j);
            if(size[rooti] > size[rootj]){
                parent[rootj] = rooti;
                size[rooti] += size[rootj];
            }
            else{
                parent[rooti] = rootj;
                size[rootj] += size[rooti];
            }
        }
    }
    
    public static long GCD(long a, long b) {
        while(b != 0){
            long temp = a;
            a = b;
            b = temp % b;
        }
        return a;
    }
    
    public static final long MOD = 1000000007;
    public static final int limit = 500005;
    
    public static class Segment{
        int l;
        int r;
        int len;
        Segment(int l, int r){
            this.l = l;
            this.r = r;
            this.len = r - l + 1;
        }
        public int getMid(){
            if(this.len % 2 == 0){
                return (this.l + this.r - 1) / 2;
            }
            return (this.l + this.r) / 2;
        }
    }
    
    public static class SegmentComparator implements Comparator<Segment>{
        public int compare(Segment a, Segment b){
            if(a.len == b.len){
                return a.l - b.l;
            }
            return b.len - a.len;
        }
    }
    
    public static void main(String[] args) {
        InputReader in = new InputReader(System.in);
        PrintWriter w = new PrintWriter(System.out);
 
        int t = in.nextInt();
        //int t=1;
        while (t-- > 0) {
            int n = in.nextInt();
            int[] A = new int[n + 1];
            
            PriorityQueue<Segment> pq = new PriorityQueue<Segment>(new SegmentComparator());
            pq.add(new Segment(1, n));
            int count = 1;
            while(!pq.isEmpty()){
                Segment seg = pq.poll();
                int i = seg.getMid();
                //System.out.println("L = " + seg.l + " R = " + seg.r + " i = " + i );
                A[i] = count++;
                if(i - 1 >= seg.l){
                    //System.out.println("Added L = " + seg.l + " R = " + (i - 1) );
                    pq.add(new Segment(seg.l, i - 1));
                }   
                if(i + 1 <= seg.r){
                    //System.out.println("Added L = " + (i + 1) + " R = " + seg.r);
                    pq.add(new Segment(i + 1, seg.r));
                }   
            }
            
            for(int i = 1; i <= n; i++) w.print(A[i] + " ");
            w.println();
        }
        w.close();
    }
    
    static class InputReader {
 
        private final InputStream stream;
        private final byte[] buf = new byte[8192];
        private int curChar, snumChars;
        private SpaceCharFilter filter;
 
        public InputReader(InputStream stream) {
            this.stream = stream;
        }
 
        public int snext() {
            if (snumChars == -1)
                throw new InputMismatchException();
            if (curChar >= snumChars) {
                curChar = 0;
                try {
                    snumChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (snumChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }
 
        public int nextInt() {
            int c = snext();
            while (isSpaceChar(c)) {
                c = snext();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = snext();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = snext();
            } while (!isSpaceChar(c));
            return res * sgn;
        }
 
        public long nextLong() {
            int c = snext();
            while (isSpaceChar(c)) {
                c = snext();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = snext();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = snext();
            } while (!isSpaceChar(c));
            return res * sgn;
        }
 
        public int[] nextIntArray(int n) {
            int a[] = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = nextInt();
            }
            return a;
        }
 
        public String readString() {
            int c = snext();
            while (isSpaceChar(c)) {
                c = snext();
            }
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = snext();
            } while (!isSpaceChar(c));
            return res.toString();
        }
 
        public String nextLine() {
            int c = snext();
            while (isSpaceChar(c))
                c = snext();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = snext();
            } while (!isEndOfLine(c));
            return res.toString();
        }
 
        public boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
 
        private boolean isEndOfLine(int c) {
            return c == '\n' || c == '\r' || c == -1;
        }
 
        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);
        }
    }
}