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:
import sys
import heapq
# from math import sqrt, floor, factorial, gcd
from collections import Counter, deque
inp = sys.stdin.readline
read = lambda: list(map(int, inp().strip().split()))



def count(n):
    s = 0
    for i in range(n//2):
        s += ((n- 2*(1+i))*4 + 4)*(n//2-i)
    return(s)


def a():
    ans = ""
    for _ in range(int(inp())):
        n, m = read()
        if n == 1:
            ans += "0\n"
        elif n == 2:
            ans += str(m)+"\n"
        else:
            ans += str(2*m)+"\n"
    print(ans)

def b():
    ans = ""
    for _ in range(int(inp())):
        n, k = read()
        a = sorted(read()); b = sorted(read(), reverse = True)
        s = 0
        for i in range(k):
            s += max(a[i], b[i])
        s += sum(a[k:])
        ans += str(s)+"\n"
    print(ans)

def c():
    ans = ""
    for _ in range(int(inp())):
        n = int(inp());
        s = 0
        if n%2:
            s = count(n)
        else:
            s = count(n-1)
        if n%2 == 0:
            s += ((2*n)-1)*(n//2)
        ans += str(s)+"\n"
    print(ans)

def d():
    ans = ""
    for _ in range(int(inp())):
        n = int(inp());
        arr = [(-n, 1, n)]; heapq.heapify(arr)
        dic = [0 for i in range(n+1)]
        num = 1
        while arr and num <= n:
            # print(arr)
            elem = heapq.heappop(arr)
            l, a, b = elem
            ind = (a+b)//2
            dic[ind] = str(num)
            num += 1
            if a!=b:
                heapq.heappush(arr, (-(ind-a+1), a, ind-1))
                heapq.heappush(arr, (-(b-ind+1), ind+1, b))
        # print(arr)
        ans += (" ").join(dic[1:])+"\n"
    print(ans)








def e():
    ans = ""
    for _ in range(int(inp())):
        n, k = read(); s = inp().strip(); dp = []
        x = 0
        for i in s:
            x += int(i)
            dp.append(x)
        min_c = 0
        for i in range(k, n):
            if s[i] == "1" and s[i-k] == "1":
                min_c += dp[i-1] - dp[i-k]
        ans += str(min_c)+"\n"
    print(ans)




if __name__ == "__main__":
	# a()
    # b()
    # c()
    d()
    # e()