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 PYTHON3):

Solution:
#include <CodeforcesSolutions.h>
#include <ONLINE_JUDGE <solution.cf(contestID = "1353",problemID = "D",method = "GET")>.h>
"""
    Author : thekushalghosh
    Team   : CodeDiggers
 
    I prefer Python language over the C++ language :p :D
        
    Visit my website : thekushalghosh.github.io
"""
import sys,math,cmath,time,bisect
from collections import deque 
start_time = time.time()
tt = 0
temp = []
#---------------------- USER DEFINED INPUT FUNCTIONS ----------------------#
def inp():
    return(int(input()))
def inlt():
    return(list(map(int,input().split())))
def insr():
    return(input().strip())
def invr():
    return(map(int,input().split()))
##########################################################################
################# ---- THE ACTUAL CODE STARTS BELOW ---- #################
 
def qw(a,q,w,qq):
    if a.get(q):
        bisect.insort(a[q],w)
    else:
        a[q] = deque([w])
        bisect.insort(qq,q)
    return(a,qq)

def qqwwqqww(a,b):
    global temp
    if a>b:
        return
    mid=(a+b)//2;temp.append((b-a,-mid));qqwwqqww(mid+1,b);qqwwqqww(a,mid-1)
    
def solve():
    n = inp()
    if n > 10 ** 5:
        global temp
        q=[0]*(n+1);temp=[];qqwwqqww(1,n);temp.sort(reverse=True);t=1
        for i in temp:q[abs(i[1])]=t;t+=1
    else:
        c = 0
        q = ["#"] + ([0] * (n))
        w = dict()
        qwqw = []
        w,qwqw = qw(w,n,[1,n],qwqw)
        for i in range(n):
            qqww = qwqw[-1]
            qq = w[qqww].popleft()
            if not w[qqww]:
                w.pop(qqww)
                qwqw.pop()
            l = qq[0]
            r = qq[1]
            ww = (l + r) // 2
            q[ww] = i + 1
            if l != r:
                if ww - l > 0:
                    w,qwqw = qw(w,ww - l,[l,ww - 1],qwqw)
                if r - ww > 0:
                    w,qwqw = qw(w,r - ww,[ww + 1,r],qwqw)
    print(*q[1:])
 
################## ---- THE ACTUAL CODE ENDS ABOVE ---- ##################
##########################################################################
def main():
    if not ONLINE_JUDGE:
        sys.stdin = open("input.txt","r")
        sys.stdout = open("output.txt","w")
    t = 1
    t = inp()
    for tt in range(t):
        solve()
    if not ONLINE_JUDGE:
        print("Time Elapsed :",time.time() - start_time,"seconds")
    sys.stdout.close()
#------------------ USER DEFINED PROGRAMMING FUNCTIONS ------------------#
def counter(a):
    q = [0] * max(a)
    for i in range(len(a)):
        q[a[i] - 1] = q[a[i] - 1] + 1
    return(q)
 
def string_counter(a):
    q = [0] * 26
    for i in range(len(a)):
        q[ord(a[i]) - 97] = q[ord(a[i]) - 97] + 1
    return(q)
ONLINE_JUDGE = __debug__
if ONLINE_JUDGE:
    input = sys.stdin.readline
    
main()