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:  Choose the maximum by length subarray (continuous subsegment) consisting only of zeros, among all such segments choose the leftmost one;  Let this segment be $[l; r]$. If $r-l+1$ is odd (not divisible by $2$) then assign (set) $a[\frac{l+r}{2}] := i$ (where $i$ is the number of the current action), otherwise (if $r-l+1$ is even) assign (set) $a[\frac{l+r-1}{2}] := i$. 

Consider the array $a$ of length $5$ (initially $a=[0, 0, 0, 0, 0]$). Then it changes as follows:  Firstly, we choose the segment $[1; 5]$ and assign $a[3] := 1$, so $a$ becomes $[0, 0, 1, 0, 0]$;  then we choose the segment $[1; 2]$ and assign $a[1] := 2$, so $a$ becomes $[2, 0, 1, 0, 0]$;  then we choose the segment $[4; 5]$ and assign $a[4] := 3$, so $a$ becomes $[2, 0, 1, 3, 0]$;  then we choose the segment $[2; 2]$ and assign $a[2] := 4$, so $a$ becomes $[2, 4, 1, 3, 0]$;  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 \le t \le 10^4$) — the number of test cases. Then $t$ test cases follow.

The only line of the test case contains one integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$ ($\sum n \le 2 \cdot 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

Difficulty: introductory

Starter code:

Solutions:
from collections import defaultdict as dd
from collections import deque
import bisect
import heapq

def ri():
    return int(input())

def rl():
    return list(map(int, input().split()))


def solve():
    n = ri()
    output = [0] * (n)

    Q = [(-n, 0 ,n - 1)]
    for i in range(1, n + 1):
        prev = heapq.heappop(Q)
        lo, hi = prev[1], prev[2]
        mid = (lo + hi) // 2
        output[mid] = i
        if mid > lo:
            heapq.heappush(Q, (-(mid - 1 - lo), lo, mid - 1))
        if hi > mid:
            heapq.heappush(Q, (-(hi - 1 - mid), mid + 1, hi))
    print(*output)





mode = 'T'

if mode == 'T':
    t = ri()
    for i in range(t):
        solve()
else:
    solve()


from heapq import heappush, heappop

for _ in range(int(input())):
    n = int(input())
    pq = [(-n, 1, n)]
    a = [0 for i in range(n + 1)]
    for i in range(1, n + 1):
        sz, l, r = heappop(pq)
        j = (l + r) // 2 if (r - l + 1) % 2 else (l + r - 1) // 2
        a[j] = i
        if j + 1 <= r:
            heappush(pq, (-(r - (j + 1) + 1), j + 1, r))
        if l <= j - 1:
            heappush(pq, (-((j - 1) - l + 1), l, j - 1))
    print(*a[1:])


import heapq
t = int(input())

for loop in range(t):

    n = int(input())

    q = []
    q.append([-1*n,0,n-1])

    ans = [0] * n
    cnt = 1

    while len(q) > 0:

        tmppop = heapq.heappop(q)
        length,l,r = tmppop
        mid = (l+r)//2

        ans[mid] = cnt
        cnt += 1

        if mid-1 >= l:
            heapq.heappush(q,[-1 * ((mid-1)-l+1) , l , mid-1])
        if mid +1 <= r:
            heapq.heappush(q,[-1 * (r-(mid+1)+1) , mid+1 , r])

    print(*ans)


import sys
import heapq as hq

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')


def solve():
    n = ni()
    a = [0]*n
    q = [(-n, 0, n-1)]
    for i in range(n):
        v, l, r = hq.heappop(q)
        m = (l + r)//2
        a[m] = i + 1
        hq.heappush(q, (-(m-l), l, m-1))
        hq.heappush(q, (-(r-m), m+1, r))
    print(*a)


# solve()

T = ni()
for _ in range(T):
    solve()


from heapq import *
t = int(input())

while t:
    t-=1
    n = int(input())
    q = []
    heappush(q,(-n,0,n-1))
    arr = [0]*n
    for i in range(n):
        # print(q)
        # print(arr)
        p = heappop(q) 
        l,r = p[1],p[2]
        mid = (l+r)//2
        arr[mid] = i+1
        if mid-l > 0:
            heappush(q,(-mid+l,l,mid-1))
        if r-mid > 0:
            heappush(q,(-r+mid,mid+1,r))
    print(*arr)

import heapq
for _ in range(int(input())):
    n=int(input())
    a=[0]*n
    que=[(-n,0,n-1)]
    heapq.heapify(que)
    i=1
    while que:
        len,l,r=heapq.heappop(que)
        if len%2==1:
            a[(l+r)//2]=i
            if r!=l:
                nl=(-(r-l)//2,l,(l+r)//2-1)
                nr=(-(r-l)//2,(l+r)//2+1,r)
                heapq.heappush(que,nl)
                heapq.heappush(que,nr)
        else:
            a[(l+r-1)//2]=i
            nl=(-(r-l-1)//2,l,(l+r-1)//2-1)
            nr=(-(r-l+1)//2,(l+r-1)//2+1,r)
            if r==l+1:
                heapq.heappush(que,nr)
            else:
                heapq.heappush(que,nr)
                heapq.heappush(que,nl)
        i+=1
    print(*a)

import heapq
import sys
input=sys.stdin.readline
from collections import defaultdict as dd
t=int(input())
while t:
    n=int(input())
    ans=[0]*n
    i=0
    j=n-1
    h=[(i-j-1,i,j)]
    heapq.heapify(h)
    ii=1
    while h:
        le,x,y=heapq.heappop(h)
        le=-le
        mid=(x+y)//2
        ans[mid]=ii
        ii+=1
        if(mid-x>0):
            heapq.heappush(h,(x-mid,x,mid-1))
        if(y-mid>0):
            heapq.heappush(h,(mid-y,mid+1,y))
    print(*ans)
    t-=1
            
        


import heapq

def solve():
    n = int(input())
    cur = 1
    a = [0] * n
    q = []
    heapq.heappush(q, (-n, 0, n))
    while q:
        _, l, r = heapq.heappop(q)
        mid = (l + r - 1) // 2
        a[mid] = cur
        cur += 1
        if l < mid:
            heapq.heappush(q, (l - mid, l, mid))
        if mid + 1 < r:
            heapq.heappush(q, ((mid + 1) - r, mid + 1, r))
    print(*a)

t = int(input())
for _ in range(t):
    solve()

for f in range(int(input())):
    n=int(input())
    segs=[[n,0]]
    sol=[0]*n
    i=0
    prev=n
    j=0
    while i<n:
        i+=1
        if j<0:
            segs.sort(reverse=True)
            j=0
            while j<len(segs) and segs[j][0]==segs[j+1][0]:
                j+=1
            prev=segs[0][0]
        m=segs[j][1]+(segs[j][0]-1)//2
        sol[m]=i
        segs.append([segs[j][0]//2,m+1])
        segs.append([(segs[j][0]-1)//2,segs[j][1]])
        segs[j][0]=0
        j-=1
    print(*sol)

import sys
input = sys.stdin.readline

def construct(A,count,MAX):
    #print(ANS,A,count,MAX)
    B=[]
    NMAX=0
    for l,r in A:
        if r-l+1==MAX:
            ANS[(r+l)//2]=count
            count+=1

            if l<=(r+l)//2-1:
                NMAX=max(NMAX,(r+l)//2-l)
                B.append((l,(r+l)//2-1))
            if r>=(r+l)//2+1:
                NMAX=max(NMAX,r-(r+l)//2)
                B.append(((r+l)//2+1,r))
        else:
            NMAX=max(NMAX,r-l+1)
            B.append((l,r))
    if NMAX!=0:
        construct(B,count,NMAX)
                
            

t=int(input())
for tests in range(t):
    n=int(input())
    ANS=[0]*n
    construct([(0,n-1)],1,n)
    print(*ANS)


import heapq

def solve(k):

    stack = [(-k,0,k-1)]  # -length, start, end (both inclusive)
    heapq.heapify(stack) 

    res = ["x" for _ in range(k)]
    cnt = 0

    while stack:
        # print(res, stack)
        cnt += 1
        length, start, end = heapq.heappop(stack)
        length = -length  # fix sign
        if length%2 == 1:  # if segment is odd length
            mid_point = (start+end)//2
            res[mid_point] = cnt
            if not start == end:
                heapq.heappush(stack, (-(mid_point-start), start, mid_point-1))
                heapq.heappush(stack, (-(mid_point-start), mid_point+1, end))
        else:  # segment is of even length
            mid_point = (start+end-1)//2
            res[mid_point] = cnt
            if length == 2:  # one other left
                heapq.heappush(stack, (-1, end, end))
            else: 
                heapq.heappush(stack, (-(length//2 - 1), start, mid_point-1))
                heapq.heappush(stack, (-(length//2), mid_point+1, end))

        # if cnt > 5:
        #     break

    # print()
    # print()
    # print()
    return " ".join([str(x) for x in res])
                


strr = input()
for _ in range(int(strr)):
    k = int(input())
    print(solve(k))


import heapq

def solve(n):
    h = [(-n, 0, n-1)]
    sol = [0]*n
    curr = 1
    while h:
        _, l, r = heapq.heappop(h)
        mid = l+(r-l)//2
        if l <= mid-1:
            heapq.heappush(h, (l-mid+1, l, mid-1))
        if r >= mid+1:
            heapq.heappush(h, (mid+1-r, mid+1, r))
        sol[mid] = curr
        curr += 1
    return sol

t = int(input())
for _ in range(t):
    n = int(input())
    # n, k = map(int, input().split())
    # a = list(map(int, input().split()))
    # b = list(map(int, input().split()))
    print(' '.join(map(str, solve(n))))