It has finally been decided to build a roof over the football field in School 179. Its construction will require placing $n$ consecutive vertical pillars. Furthermore, the headmaster wants the heights of all the pillars to form a permutation $p$ of integers from $0$ to $n - 1$, where $p_i$ is the height of the $i$-th pillar from the left $(1 \le i \le n)$.

As the chief, you know that the cost of construction of consecutive pillars is equal to the maximum value of the bitwise XOR of heights of all pairs of adjacent pillars. In other words, the cost of construction is equal to $\max\limits_{1 \le i \le n - 1}{p_i \oplus p_{i + 1}}$, where $\oplus$ denotes the bitwise XOR operation .

Find any sequence of pillar heights $p$ of length $n$ with the smallest construction cost.

In this problem, a permutation is an array consisting of $n$ distinct integers from $0$ to $n - 1$ in arbitrary order. For example, $[2,3,1,0,4]$ is a permutation, but $[1,0,1]$ is not a permutation ($1$ appears twice in the array) and $[1,0,3]$ is also not a permutation ($n=3$, but $3$ is in the array).


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). Description of the test cases follows.

The only line for each test case contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of pillars for the construction of the roof.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.


-----Output-----

For each test case print $n$ integers $p_1$, $p_2$, $\ldots$, $p_n$ — the sequence of pillar heights with the smallest construction cost.

If there are multiple answers, print any of them.


-----Examples-----

Input
4
2
3
5
10
Output
0 1
2 0 1
3 2 1 0 4
4 6 3 2 0 8 9 1 7 5


-----Note-----

For $n = 2$ there are $2$ sequences of pillar heights:

$[0, 1]$ — cost of construction is $0 \oplus 1 = 1$.

$[1, 0]$ — cost of construction is $1 \oplus 0 = 1$.

For $n = 3$ there are $6$ sequences of pillar heights:

$[0, 1, 2]$ — cost of construction is $\max(0 \oplus 1, 1 \oplus 2) = \max(1, 3) = 3$.

$[0, 2, 1]$ — cost of construction is $\max(0 \oplus 2, 2 \oplus 1) = \max(2, 3) = 3$.

$[1, 0, 2]$ — cost of construction is $\max(1 \oplus 0, 0 \oplus 2) = \max(1, 2) = 2$.

$[1, 2, 0]$ — cost of construction is $\max(1 \oplus 2, 2 \oplus 0) = \max(3, 2) = 3$.

$[2, 0, 1]$ — cost of construction is $\max(2 \oplus 0, 0 \oplus 1) = \max(2, 1) = 2$.

$[2, 1, 0]$ — cost of construction is $\max(2 \oplus 1, 1 \oplus 0) = \max(3, 1) = 3$.

Source: codeforces | Difficulty: EASY
Tags: Bit manipulation

Constructive algorithms


Solutions:
from sys import stdin

def solve():
	pows2 = set()
	x = 1
	while x < 10 ** 6:
		pows2.add(x)
		x *= 2
	for _ in range(int(stdin.readline().strip())):
		n = int(stdin.readline().rstrip())
		A = list(range(n))[::-1]
		flag = 0
		for i in range(n):
			if A[i] in pows2:
				B = A[i + 1:] + A[:i + 1][::-1]
				break
		print(' '.join(map(str, B)))
solve()


import sys

def getline() -> str:
	return sys.stdin.readline().strip()

def solve():
	n = int(getline()) - 1
	bits = str(bin(n))[2:]
	highest = 1 << len(bits) - 1
	sol = list(range(1, n + 1))
	sol.insert(highest - 1, 0)
	print(' '.join(map(str, sol)))
t = int(getline())
for _ in range(t):
	solve()


n = int(input())
results = []
while n:
	pillers = int(input())
	k = 1
	while k < pillers:
		k = k * 2
	k = k // 2
	pillerSet = [str(i) for i in range(k - 1, 0, -1)]
	pillerSet.append('0')
	for i in range(k, pillers):
		pillerSet.append(str(i))
	results.append(pillerSet)
	n -= 1
for i in results:
	print(' '.join(i))


import sys
FILE = None
if FILE:
	sys.stdin = open(FILE, 'r')
input = sys.stdin.readline

def inp():
	return int(input())

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

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
for _ in range(int(input())):
	n = inp()
	pow = 0
	cur = 1
	while cur * 2 < n:
		pow += 1
		cur *= 2
	arr = []
	for i in range(1, cur):
		arr.append(i)
	arr.append(0)
	for i in range(cur, n):
		arr.append(i)
	print(' '.join([str(item) for item in arr]))


import math as m
tc = int(input())
for i in range(tc):
	x = int(input())
	if x == 2:
		print('0 1')
	elif x == 3:
		print('2 0 1')
	else:
		list1 = []
		a = 2 ** int(m.log(x - 1, 2))
		for i in range(2, a):
			list1 += [i]
		list1 += [1, 0]
		for i in range(a, x):
			list1 += [i]
		list1 = str(list1)
		list1 = list1.replace(',', '')
		list1 = list1.replace('[', '')
		list1 = list1.replace(']', '')
		print(list1)


import sys
import math
from typing import List
input = sys.stdin.readline

def solution() -> List[str]:
	std = 2 ** int(math.log2(n - 1))
	res = [str(num) for num in range(std - 1, -1, -1)]
	for num in range(std, n):
		res.append(str(num))
	return res
t = int(input())
for tc in range(t):
	n = int(input())
	sol = solution()
	print(' '.join(sol))


for iters in range(int(input())):
	n = int(input())
	msb = 0
	m = n - 1
	while m != 0:
		msb += 1
		m //= 2
	s = [str(i) for i in range(2 ** (msb - 1))]
	s.reverse()
	e = [str(i) for i in range(2 ** (msb - 1), n)]
	final = s + e
	print(' '.join(final))


def solve(n):
	res = []
	boundary = 1
	while boundary * 2 <= n - 1:
		boundary = boundary * 2
	for i in range(n - 1, boundary - 1, -1):
		res.append(i)
	res.append(0)
	for i in range(1, boundary):
		res.append(i)
	r = ' '.join(list(map(str, res)))
	return r
test = int(input())
for t in range(0, test):
	n = int(input())
	print(solve(n))


for _ in range(int(input())):
	n = int(input())
	t = n - 1
	count = 0
	l = []
	while t != 1:
		t = t // 2
		count += 1
	l = [i for i in range(2 ** count)]
	l.reverse()
	for i in range(2 ** count, n):
		l.append(i)
	l = [str(i) for i in l]
	print(' '.join(l))


import math
t = int(input())
for i in range(t):
	n = int(input())
	m = 1
	while m * 2 <= n - 1:
		m = 2 * m
	l = list(range(1, m)) + [0, m] + list(range(m + 1, n))
	print(' '.join((str(c) for c in l)))


import sys

def f(x):
	if x == 0:
		return [0]
	elif x == 1:
		return [0, 1]
	z = 1
	while z * 2 <= x:
		z *= 2
	print('z', x, z)
	a = list(range(z))
	for v in f(x - z):
		a.append(z | v)
	return a

def solve():
	inp = sys.stdin.readline
	n = int(inp())
	z = 1
	while z * 2 <= n - 1:
		z *= 2
	p = list(range(z - 1, -1, -1)) + list(range(z, n))
	z = 0
	for i in range(1, n):
		z = max(z, p[i] ^ p[i - 1])
	print(' '.join(map(str, p)))

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


import math
T = int(input())
for i in range(T):
	answer = []
	N = int(input())
	n = 2 ** int(math.log2(N - 1))
	answer.append(str(0))
	answer.append(str(n))
	count = 1
	while n + count < N:
		if count % 2 == 1:
			answer.append(str(n + count))
			answer.append(str(count))
		else:
			answer.append(str(count))
			answer.append(str(n + count))
		count += 1
	front_answer = []
	for i in range(count, n):
		front_answer.append(str(i))
	print(' '.join(front_answer + answer))


import itertools
import math

def xor(p):
	return max((x ^ y for (x, y) in zip(p, p[1:])))

def min_xor(permutations):
	return min((xor(p) for p in permutations))

def naive(n):
	permutations = list(itertools.permutations(range(n)))
	minimum = min_xor(permutations)
	return [p for p in permutations if xor(p) == minimum]

def solution(n):
	return ' '.join((str(v) for v in itertools.chain(range(n, 2 ** int(math.log2(n)) - 1, -1), [0], range(2 ** int(math.log2(n)) - 1, 0, -1))))

def read_int():
	return int(input().strip())

def main():
	for i in range(read_int()):
		print(solution(read_int() - 1))
main()


for t in range(int(input())):
	n = int(input())
	i = 1
	while 2 * i < n:
		i *= 2
	arr = [x for x in range(i - 1, -1, -1)] + [x for x in range(i, n)]
	print(' '.join(map(str, arr)))


from math import log2, floor
tc = int(input())
for t in range(tc):
	n = int(input())
	lhs = 1 << floor(log2(n - 1))
	arr = list()
	for i in range(lhs - 1, -1, -1):
		arr.append(i)
	for i in range(lhs, n):
		arr.append(i)
	print(' '.join((str(i) for i in arr)))


t = int(input())
for i in range(t):
	n = int(input())
	x = len(bin(n - 1)) - 2
	(res, eta) = ([], [])
	c = 2 ** (x - 1)
	for j in range(c):
		res.append(j)
	for j in range(c, n):
		eta.append(j)
	res = res[::-1] + eta
	print(' '.join([str(k) for k in res]))


for _ in range(int(input())):
	n = int(input())
	base = 1
	while 2 * base <= n - 1:
		base *= 2
	res = []
	for i in range(n - 1, 0, -1):
		res.append(str(i))
		if i == base:
			res.append('0')
	print(' '.join(res))


for _ in range(int(input())):
	n = int(input())
	m = n - 1
	cnt = 0
	arr = []
	s = m
	while m > 0:
		m //= 2
		cnt += 1
	y = cnt - 1
	x = 2 ** y
	for i in range(s, x - 1, -1):
		arr.append(i)
	for j in range(x):
		arr.append(j)
	str_arr = [str(x) for x in arr]
	print(' '.join(str_arr))


import sys
import re
import math
from math import log2 as lg
from math import gcd
from decimal import *
from collections import deque
import random
import heapq
import itertools
import datetime
const = 1000000007
ep = 1e-08

def get():
	return list(map(int, input().split()))
n = int(input())
for i in range(n):
	m = int(input())
	lst = []
	largest = 1
	while largest * 2 < m:
		largest *= 2
	for j in range(m - 1, largest - 1, -1):
		lst.append(str(j))
	for j in range(0, largest):
		lst.append(str(j))
	print(' '.join(lst))


N = int(input())
for _ in range(N):
	n = int(input())
	if n == 2:
		print('0 1')
	else:
		a = [-1] * n
		h = (n - 1).bit_length() - 1
		if n - 1 == 1 << h:
			a[0] = n - 1
			for i in range(n - 1):
				a[i + 1] = i
		else:
			a[0] = 0
			a[1] = 1 << h
			for i in range(n - (1 << h) - 1):
				a[i + 2] = i + (1 << h) + 2
			a[n - (1 << h)] = (1 << h) + 1
			for i in range((1 << h) - 1):
				a[n - (1 << h) + 1 + i] = i + 1
		print(' '.join(map(str, a)))


import sys

def solve():
	n = int(input())
	x = 2
	while x * 2 < n:
		x <<= 1
	for i in range(x - 1, -1, -1):
		sys.stdout.write(f'{i} ')
	for i in range(x, n):
		sys.stdout.write(f'{i} ')
	sys.stdout.write('\n')
t = int(input())
for _ in range(t):
	solve()


from math import log, floor
k = int(input())
for i in range(k):
	n = int(input())
	significant = int(2 ** floor(log(n, 2)))
	if significant == n:
		significant = int(2 ** floor(log(n - 1, 2)))
	m = n - significant
	a = list(reversed(range(significant + 1, n, 2)))
	a = a + list(reversed(range(significant, n, 2)))
	a.append(0)
	a = a + list(range(1, significant))
	print(' '.join(map(str, a)))


t = int(input())
for _ in range(t):
	n = int(input())
	k = (n - 1).bit_length()
	u = 1 << k - 1
	upper = []
	for i in range(1, u):
		if i != n - 1 - u:
			upper.append(str(i))
	upper.append('0')
	for i in range(u, n):
		upper.append(str(i))
	if n - 1 - u != 0:
		upper.append(str(n - 1 - u))
	print(' '.join(upper))


def function(n):
	import math
	arr = [str(i) for i in range(n)]
	if n < 3:
		return ' '.join(arr)
	for i in range(n - 1, -1, -1):
		val = math.log(i, 2)
		if 2 ** int(val) == i:
			arr[i - 1] = '0'
			arr[0] = str(i - 1)
			break
	return ' '.join(arr)
t = int(input())
for _ in range(t):
	n = int(input())
	print(function(n))


import math
for i in range(int(input())):
	output = ''
	n = int(input())
	log = int(math.log(n - 1, 2))
	for i in range(1, 2 ** log):
		output += str(i) + ' '
	output += '0 '
	for i in range(2 ** log, n):
		output += str(i) + ' '
	print(output)


t = int(input())
ii = 0
for ii in range(0, t):
	n = int(input())
	if n == 2:
		print('0 1')
	else:
		maxp = 2
		while maxp <= n - 1:
			maxp = maxp * 2
		maxp = int(maxp / 2)
		s = ''
		i = n - 1
		while i >= maxp:
			s += str(i) + ' '
			i -= 1
		i = 0
		while i < maxp:
			s += str(i) + ' '
			i += 1
		print(s.strip())


import sys
input = sys.stdin.readline
import math
for _ in range(int(input())):
	n = int(input())
	x = 2 ** int(math.log(n, 2))
	if n != x:
		d = list(range(x - 1, -1, -1)) + list(range(x, n))
	else:
		d = list(range(x // 2 - 1, -1, -1)) + list(range(x // 2, n))
	print(*d)


for i in range(int(input())):
	a = int(input())
	s = 1
	while 2 * s <= a - 1:
		s *= 2
	ans = ''
	for i in range(s - 1, -1, -1):
		ans += str(i) + ' '
	for i in range(s, a):
		ans += str(i) + ' '
	print(ans[:-1])


t = int(input())
for _ in range(t):
	n = int(input()) - 1
	l = n.bit_length()
	a = 1 << l - 1
	s = ''
	for i in range(a - 1, -1, -1):
		s += str(i) + ' '
	for i in range(a, n + 1):
		s += str(i) + ' '
	print(s.strip())


cases = int(input())
while cases > 0:
	n = int(input())
	n -= 1
	temp = n
	c = 0
	while temp > 0:
		c += 1
		temp = int(temp / 2)
	j = 1
	c -= 1
	while c > 0:
		j *= 2
		c -= 1
	ans = ''
	while n >= j:
		ans += str(n) + ' '
		n -= 1
	i = 0
	while i < j:
		ans += str(i) + ' '
		i += 1
	print(ans)
	cases -= 1


from collections import Counter
import heapq
tt = int(input())
for i in range(tt):
	n = int(input())
	p = 1
	while p << 1 < n:
		p <<= 1
	ans = ''
	for i in range(p - 1, -1, -1):
		ans += str(i) + ' '
	ans += str(p)
	for i in range(p + 1, n):
		ans += ' ' + str(i)
	print(ans)


from math import log2
t = int(input())
res = []
for _ in range(t):
	n = int(input())
	n -= 1
	k = 2 ** int(log2(n))
	r = [i for i in range(1, k)] + [0, k] + [i for i in range(k + 1, n + 1)]
	res.append(r)
for i in res:
	print(*i)


import math
from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	n = int(input())
	xyz = int(math.log2(n - 1))
	maxi = 2 ** xyz
	b = []
	for i in range(1, maxi):
		b.append(i)
	b.append(0)
	b.append(maxi)
	for i in range(maxi + 1, n):
		b.append(i)
	print(*b)


import math
cases = int(input())
while cases > 0:
	n = int(input())
	n -= 1
	ans = ''
	po = pow(2, int(math.log2(n)))
	while n >= po:
		ans += str(n) + ' '
		n -= 1
	i = 0
	while i < po:
		ans += str(i) + ' '
		i += 1
	print(ans)
	cases -= 1


from math import log2, floor
import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = 2 ** floor(log2(n - 1))
	for x in range(1, a):
		print(x, end=' ')
	print(0, a, end=' ')
	for x in range(a + 1, n):
		print(x, end=' ')
	print()


import sys
input = sys.stdin.readline

def solution():
	n = int(input())
	d = 1
	while 2 * d < n:
		d *= 2
	for i in range(n - 1, d - 1, -1):
		print(i, end=' ')
	print(0, end=' ')
	for i in range(d - 1, 0, -1):
		print(i, end=' ')
	print()

def main():
	t = 1
	t = int(input())
	for i in range(t):
		solution()
main()


import sys
input = sys.stdin.readline
t = int(input().strip())
for _ in range(t):
	n = int(input().strip())
	n -= 1
	cnt = 0
	tmp = n
	while tmp != 1:
		tmp //= 2
		cnt += 1
	ret = 2 ** cnt
	lst = []
	for i in range(1, ret):
		lst.append(i)
	lst += [0, ret]
	for i in range(ret + 1, n + 1):
		lst.append(i)
	print(*lst)


import sys
t = int(input())
for _ in range(t):
	n = int(input())
	x = 2
	while x * 2 < n:
		x <<= 1
	for i in range(x - 1, -1, -1):
		sys.stdout.write(str(i) + ' ')
	for i in range(x, n):
		sys.stdout.write(str(i) + ' ')
	sys.stdout.write('\n')


def cutpoint(n):
	i = 1
	while n > 1:
		n >>= 1
		i <<= 1
	return i
for _ in range(int(input())):
	n = int(input())
	c = cutpoint(n - 1)
	L = list(range(c - 1, -1, -1)) + list(range(c, n))
	print(*L)


for _ in range(int(input())):
	n = int(input())
	k = 1
	i = n - 1
	while i > 1:
		i //= 2
		k += k
	print(*range(1, k), 0, *range(k, n))


import sys
input = sys.stdin.readline
T = int(input())
for t in range(T):
	n = int(input())
	binary = 1
	while binary * 2 < n:
		binary *= 2
	for x in range(n - 1, binary - 1, -1):
		print(x, end=' ')
	for x in range(binary):
		print(x, end=' ')
	print()


for tc in range(int(input())):
	n = int(input())
	arr = [i for i in range(n)]
	po = 0
	n -= 1
	while 2 ** po <= n:
		po += 1
	po -= 1
	ind = arr.index(2 ** po)
	arr.pop(0)
	arr.insert(ind - 1, 0)
	print(*arr, sep=' ')


import math
for _ in range(int(input())):
	n = int(input())
	ans = []
	l = math.log(n - 1, 2)
	l = int(l)
	po = 1 << l
	ans = []
	for i in range(1, po):
		ans.append(i)
	ans.append(0)
	for i in range(po, n):
		ans.append(i)
	print(*ans)


import sys, collections

def solve(n):
	mx = n - 1
	if mx & mx - 1 == 0:
		return [i for i in range(1, mx)] + [0, mx]
	s = bin(mx)[2:]
	v = int('1' + '0' * (len(s) - 1), 2)
	return [i for i in range(1, v)] + [0, v] + [i for i in range(v + 1, mx + 1)]
input = sys.stdin.readline
tests = int(input()[:-1])
for test in range(tests):
	n = int(input()[:-1])
	arr = solve(n)
	print(*arr)


import sys
input = sys.stdin.readline
from math import log2

def solve(n):
	ans = [i for i in range(n)]
	z = 2 ** int(log2(n - 1))
	first = ans[:z]
	first.reverse()
	return first + ans[z:]
t = int(input())
for _ in range(t):
	n = int(input())
	print(*solve(n))


def main():
	n = int(input())
	x = 1
	while x * 2 < n:
		x *= 2
	A = list(range(1, x)) + [0] + list(range(x, n))
	print(*A)

def xor(x, y):
	a = bin(x)[2:]
	b = bin(y)[2:]
	lngth = max(len(a), len(b))
	a = '0' * (lngth - len(a)) + a
	b = '0' * (lngth - len(b)) + b
	c = int(''.join(['1' if a[i] != b[i] else '0' for i in range(lngth)]), 2)
	return c

def coast(A):
	m = -1
	for i in range(len(A) - 1):
		m = max(m, xor(A[i], A[i + 1]))
	for i in range(len(A)):
		a = bin(A[i])[2:]
	return m
t = int(input())
for _ in range(t):
	main()


powers = [2 ** i for i in range(18)]
out = []
for _ in range(int(input())):
	n = int(input())
	p = 17
	while powers[p] >= n:
		p -= 1
	ans = [i for i in range(n - 1, powers[p] - 1, -1)]
	ans.append(0)
	ans += [i for i in range(powers[p] - 1, 0, -1)]
	out.append(ans)
for i in out:
	print(*i)


t = int(input())
for i in range(0, t):
	n = int(input())
	a = 0
	s = ''
	for j in range(0, n):
		if 2 ** j > n - 1:
			a = 2 ** (j - 1)
			break
	s += str(a) + ' 0 '
	if a == n - 1:
		for l in range(1, n):
			if l != a:
				s += str(l) + ' '
	else:
		for p in range(1, n):
			if p == a + 1:
				s += '1 '
				s += str(p) + ' '
			elif p == 1 or p == a:
				continue
			else:
				s += str(p) + ' '
	s.rstrip()
	print(s)


import math
import sys
input = sys.stdin.readline

def inp():
	return int(input())
t = inp()
while t > 0:
	n = inp()
	p = []
	if n == 2:
		p = [1, 0]
	else:
		curr = n - 1
		while True:
			p.append(curr)
			if math.log(curr, 2).is_integer():
				break
			else:
				curr -= 1
		for i in range(curr):
			p.append(i)
	print(*p)
	t -= 1


for _ in range(int(input())):
	n = int(input()) - 1
	z = 1 << n.bit_length() - 1
	print(*range(z - 1, -1, -1), *range(z, n + 1))


for _ in range(int(input())):
	n = int(input()) - 1
	k = n.bit_length() - 1
	i = 2 ** k
	print(*range(i - 1, -1, -1), *range(i, n + 1))


import math
for _ in range(int(input())):
	n = int(input())
	x = int(math.log2(n - 1))
	l = list(range(1, 2 ** x, 1)) + [0] + list(range(2 ** x, n, 1))
	print(*l)


num_inp = lambda : int(input())
arr_inp = lambda : list(map(int, input().split()))
sp_inp = lambda : map(int, input().split())
str_inp = lambda : input()
for _ in range(int(input())):
	n = int(input()) - 1
	z = 1 << n.bit_length() - 1
	print(*range(z - 1, -1, -1), *range(z, n + 1))


cas = int(input())
for i in range(cas):
	n = int(input())
	k = 1
	c = n - 1
	while c > 1:
		c = c // 2
		k = k + k
	print(*range(1, k), 0, *range(k, n))


from math import log2
for _ in range(int(input())):
	n = int(input())
	a = int(log2(n - 1))
	k = 2 ** a
	print(*range(1, k), 0, *range(k, n))


import math
power = [2 ** i for i in range(2, 22)]
for _ in range(int(input())):
	n = int(input())
	ans = ''
	if n - 1 in power:
		for i in range(n - 1):
			ans += str(i) + ' '
		ans = str(n - 1) + ' ' + ans
	else:
		cek = True
		tmp = 2 ** 30
		for i in power:
			if i > n - 1:
				tmp = i
				tmp = tmp // 2
				break
		for i in range(1, n):
			if i == tmp - 1:
				ans += str(i) + ' 0 '
			else:
				ans += str(i) + ' '
	if n == 3:
		print('2 0 1')
	elif n == 2:
		print('0 1')
	else:
		print(ans)


for _ in range(int(input())):
	a = int(input())
	r = list(range(a))
	a -= 1
	msb = 1
	while msb << 1 <= a:
		msb = msb << 1
	r[0] = msb - 1
	r[msb - 1] = 0
	print(*r)


import math
from math import floor
for tc in range(int(input())):
	n = int(input())
	ans = []
	lln = bin(n - 1)[2:]
	lln = 2 ** (len(lln) - 1)
	ans.extend(list(range(n - 1, lln - 1, -1)))
	ans.extend(list(range(0, lln)))
	print(*ans, sep=' ')


from math import log2
for _ in range(int(input())):
	n = int(input())
	l = 2 ** int(log2(n - 1))
	p = [*range(1, l)] + [0] + [*range(l, n)]
	print(*p)


def solve(x):
	pow = 1
	while x >= 2 * pow:
		pow *= 2
	ret = []
	for i in reversed(range(pow, x + 1)):
		ret.append(i)
	ret.append(0)
	for i in range(1, pow):
		ret.append(i)
	return ret
t = int(input())
for _ in range(t):
	x = int(input())
	print(*solve(x - 1), sep=' ')


from collections import Counter, deque
from itertools import accumulate, product, groupby
import operator
import math
from functools import reduce

def solve():
	n = int(input())
	if n == 2:
		return [0, 1]
	i = 1
	n2 = 2
	while n2 <= n:
		n2 *= 2
		i += 1
	if n & n - 1 == 0:
		n2 //= 2
	n2 //= 2
	ans = []
	for i in range(n - 1, n2 - 1, -1):
		ans.append(i)
	ans.append(0)
	for i in range(n2 - 1, 0, -1):
		ans.append(i)
	return ans
for _ in range(int(input())):
	print(*solve())


t = int(input())
for i in range(t):
	n = int(input()) - 1
	binary = bin(n)
	length = len(binary) - 2
	min_cost = 2 ** (length - 1)
	arr = list(range(1, min_cost))
	arr.append(0)
	arr2 = list(range(min_cost, n + 1))
	final = arr + arr2
	print(*final)


t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	j = 1
	while j * 2 < n:
		j *= 2
	for i in range(1, j):
		print(i, end=' ')
	print(0, end=' ')
	for i in range(j, n):
		print(i, end=' ')
	print()


for i in range(0, int(input())):
	l = []
	n = int(input())
	k = bin(n - 1)[2:]
	k = 2 ** (len(k) - 1)
	l.extend(list(range(n - 1, k - 1, -1)))
	l.extend(list(range(0, k)))
	print(*l, sep=' ')


from math import log, ceil
for _ in range(int(input())):
	n = int(input())
	l = ceil(log(n, 2))
	print(*list(range(2 ** (l - 1) - 1, -1, -1)), *list(range(2 ** (l - 1), n)))


from collections import Counter, deque, defaultdict
from itertools import accumulate, product, groupby
import operator
import math
from functools import reduce

def solve():
	n = int(input())
	bin_string = bin(n - 1)[2:]
	bs = len(bin_string)
	mid = '1' + '0' * (bs - 1)
	mid_val = int(mid, 2)
	left = list(range(mid_val - 1, -1, -1))
	right = list(range(mid_val, n))
	return left + right
for _ in range(int(input())):
	print(*solve())


for _ in range(int(input())):
	n = int(input())
	l = []
	if n == 2:
		print(*[0, 1])
		continue
	for i in range(32):
		if n <= 2 ** i:
			k = 2 ** (i - 1)
			break
	for i in range(k - 1, -1, -1):
		l.append(i)
	l.append(k)
	for i in range(k + 1, n):
		l.append(i)
	print(*l)


from math import log2
for _ in range(int(input())):
	n = int(input())
	a = []
	b = int(log2(n - 1))
	c = 2 ** b
	for i in range(c - 1, -1, -1):
		a.append(i)
	for i in range(c, n):
		a.append(i)
	print(*a)


import math
t = int(input())
for tt in range(t):
	n = int(input())
	n = n - 1
	logn = int(math.log(n, 2))
	b = 2 ** logn
	arr = []
	for i in range(n, b - 1, -1):
		arr.append(i)
	arr.append(0)
	arr += [i for i in range(b - 1, 0, -1)]
	print(*arr)


def get_closest_power_of_2(n):
	x = 1
	while 2 * x < n:
		x *= 2
	return x

def print_sequence(n):
	closest_power = get_closest_power_of_2(n)
	for i in range(1, closest_power):
		print(i, end=' ')
	print(0, end=' ')
	for i in range(closest_power, n):
		print(i, end=' ')
	print()
t = int(input())
for i in range(t):
	n = int(input())
	print_sequence(n)


import sys
input = sys.stdin.readline
MAX = sys.maxsize
sys.setrecursionlimit(10 ** 9)

def inp():
	return int(input())

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

def read_list():
	s = input()
	return list(s[:len(s) - 1])

def read_int_map():
	return map(int, input().split())

def solve(n):
	x = 1
	while x < n:
		x <<= 1
	rev = x >> 1
	for i in range(rev - 1, -1, -1):
		print(f'{i} ', end='')
	for i in range(rev, n):
		print(f'{i} ', end='')
	print()
for _ in range(inp()):
	solve(inp())


a = [1]
x = 1
for i in range(1, 20):
	x = x * 2
	a.append(x)
for l in range(int(input())):
	n = int(input())
	n -= 1
	for i in range(20):
		if a[i] > n:
			x = a[i - 1]
			break
	print(*range(n, x - 1, -1), 0, *range(x - 1, 0, -1))


for _ in range(int(input())):
	n = int(input())
	k = 1
	while k << 1 < n:
		k <<= 1
	print(*range(k - 1, -1, -1), *range(k, n))


from math import *
for _ in range(int(input())):
	N = int(input())
	r = 1 << int(log2(N - 1))
	print(*list(range(N - 1, r - 1, -1)) + list(range(r)))


t = int(input())
for _ in range(t):
	n = int(input())
	k = n
	n -= 1
	while n & n - 1 != 0:
		n -= 1
	arr = list(range(n - 1, -1, -1)) + list(range(n, k))
	print(*arr)


def highestPowerof2(x):
	x |= x >> 1
	x |= x >> 2
	x |= x >> 4
	x |= x >> 8
	x |= x >> 16
	return x ^ x >> 1
for _ in range(int(input())):
	n = int(input())
	hp = highestPowerof2(n - 1)
	l = []
	for i in range(1, hp):
		l.append(i)
	l.append(0)
	for i in range(hp, n):
		l.append(i)
	print(*l)


for _ in range(int(input())):
	n = int(input())
	if n == 2:
		print(1, 0)
	else:
		i = 1
		n2 = 2
		while n2 <= n:
			n2 *= 2
			i + 1
		if n & n - 1 == 0:
			n2 //= 2
		n2 //= 2
		for k in range(n - 1, n2 - 1, -1):
			print(k, end=' ')
		print(0, end=' ')
		for k in range(n2 - 1, 0, -1):
			print(k, end=' ')
		print()


import math
t = int(input())
for _ in range(t):
	n = int(input()) - 1
	k = int(math.log(n, 2))
	k = pow(2, k)
	for i in range(1, k):
		print(i, end=' ')
	print(0, k, end=' ')
	for i in range(k + 1, n + 1):
		print(i, end=' ')
	print()


import sys
from math import sqrt, gcd
from collections import deque, Counter, OrderedDict
sys.setrecursionlimit(10 ** 8)
I = lambda : int(input())
S = lambda : input().strip()
M = lambda : map(int, input().strip().split())
L = lambda : list(map(str, input().strip().split()))
mod = 1000000007
for i in range(I()):
	n = I()
	k = 1
	while k * 2 <= n - 1:
		k *= 2
	ans = [i + 1 for i in range(k - 1)] + [0] + [i for i in range(k, n)]
	print(*ans)


for _ in range(int(input())):
	n = int(input())
	k = len(bin(n - 1)[2:])
	l = pow(2, k - 1)
	lst = []
	x = n - 1
	while x >= l:
		lst.append(x)
		x -= 1
	for i in range(l):
		lst.append(i)
	print(*lst)


def solve(n):
	if n == 2:
		print('0 1')
		return
	ans = []
	nums = set([i for i in range(n)])
	v = 2 ** (len(bin(n - 1)) - 3)
	for i in range(n - 1, v - 1, -1):
		ans.append(i)
		nums.remove(i)
	ans.append(0)
	nums.remove(0)
	for num in nums:
		ans.append(num)
	print(*ans)
for _ in range(int(input())):
	solve(int(input()))