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:
class node():
	def __init__(self, val):
		self.left = None
		self.right = None
		self.ind = val
		self.range = (0,0)
from heapq import heappop, heappush
class Node():
	def __init__(self, vec):
		self.vec = vec
	def __lt__(self, other):
		if other.vec[0]>self.vec[0]:
			inv = False
			left, right = (self, other)
		else:
			inv = True
			left, right = (other, self)
		if (-left.vec[0]+left.vec[1]+1)<(-right.vec[0]+right.vec[1]+1):
			# print(left.vec, right.vec, "report")
			if inv==False:
				return False
			return True
		if inv == False:
			return True
		return False
for t in range(int(input())):
	n = int(input())
	lf = 0
	rt = n-1
	l = [0 for i in range(n)]
	stack = []
	heappush(stack, Node((lf, rt)))
	i = 0
	while(stack):
		i+=1
		if i>n:
			break
		# print(stack)
		root = heappop(stack)
		root = root.vec
		if (root[1]-root[0]+1)%2==0:
			mid = (root[0]+root[1]-1)//2 
		else:
			mid = (root[0]+root[1])//2 

		l[mid] = i
		
		if root[0]==root[1]:
			# print("alone", mid)
			continue
		left = (root[0], mid-1)
		right = (mid+1, root[1])
		if (-left[0]+left[1]+1)<(-right[0]+right[1]+1):
			heappush(stack, Node(right))
			heappush(stack, Node(left))
		else:
			heappush(stack, Node(left))
			heappush(stack, Node(right))
		# print(mid, root, l, i) 
	# 
	for i in range(n):
		print(l[i], end =" ")
	print()
	# print(l)




































	# n = int(input())
	# if n%2==0:
	# 	root = node((n-2)//2)
	# else:
	# 	root = node((n-1)//2)
	# # root.ind = 

	# # lf = 0
	# # rt = n-1
	# # root.range = (lf, rt)
	# # main_root = root
	# # stack = [root]
	# # yt = 0
	# # while(stack):
	# # 	yt+=1
	# # 	root = stack.pop(0)
	# # 	print(root.ind, "ind")
	# # 	mid = root.ind
	# # 	if root.range[0]==root.range[1]:
	# # 		continue
	# # 	if (root.range[0]+mid)%2==0:
	# # 		if (root.range[0]+mid-2)>-1:
	# # 			root.left = node((root.range[0]+mid-2)//2)
	# # 	else:
	# # 		if ((root.range[0]+mid-1)//2)%2>-1:
	# # 			root.left = node((root.range[0]+mid-1)//2)
	# # 	if (root.range[1]+mid+2)%2==0:
	# # 		if ((root.range[1]+mid)//2)<n:
	# # 			root.right = node((root.range[1]+mid)//2)
	# # 	else:
	# # 		if ((root.range[1]+mid+1)//2)<n:
	# # 			root.right = node((root.range[1]+mid+1)//2)
	# # 	# print(root.left.ind, root.right.ind, root.range[1], root.range[0])
	# # 	if root.left:
	# # 		root.left.range = (root.range[0],mid-1)
	# # 		stack.append(root.left)
	# # 	if root.right:
	# # 		root.right.range = (mid+1, root.range[1])
	# # 		stack.append(root.right)
		
	# # 	if yt>6:
	# # 		break
	# # ct = 0
	# # root = main_root
	# # ans = [i for i in range(n)]
	# # stack = [root]
	# while(stack!=[]):
	# 	# try:
	# 	# 	for r in stack:
	# 	# 		print(r.ind, end = ' ')
	# 	# 	print()
	# 	# except:
	# 	# 	pass
	# 	ct+=1
	# 	root = stack.pop(0)
	# 	if root==None:
	# 		ct-=1
	# 		continue
	# 	ans[root.ind] = ct
	# 	if root.range[0]==root.range[1]:
	# 		continue
	# 	if (root.range[1]-root.range[0]+1)%2==0:
	# 		stack.append(root.right)
	# 		stack.append(root.left)
	# 	else:
	# 		stack.append(root.left)
	# 		stack.append(root.right)		
	# # print(lsit(map(str,ans), sep = ' ')
	# # print(, sep =' ')
	# for i in range(len(ans)):	
	# 	print(ans[i], end = ' ')
	# print()




	# tree = [[0,]]
	# l = [int(j) for j in input().split()]