M. Maximum Or Permutation
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an integer $$$n$$$. Your task is to construct a permutation $$$p$$$ of the set $$$\{1, 2, \dots, n\}$$$ such that when the permutation is considered as circular (i.e. $$$p_1$$$ and $$$p_n$$$ are adjacent), the maximum bitwise OR over all adjacent pairs is minimized.

Formally, for a permutation $$$p = [p_1, p_2, \dots, p_n]$$$, define

$$$f(p) = \max_{1 \le i \le n} \Bigl( p_i \; | \; p_{i+1} \Bigr)$$$,

where we define $$$p_{n+1} = p_1$$$ and $$$|$$$ denotes the bitwise OR operation. Your goal is to construct a permutation $$$p$$$ such that $$$f(p)$$$ is as small as possible.

If there are multiple answers, you may output any one of them.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases.

Each of the following $$$t$$$ lines contains a single integer $$$n$$$ ($$$2 \le n \le 5 \cdot 10^5$$$) — the size of the permutation.

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

Output

For each test case, output a permutation of $$$\{1,2,\dots,n\}$$$ (i.e. a sequence of $$$n$$$ distinct integers) such that the maximum bitwise OR of any two adjacent elements (considering the permutation circularly) is minimized.

Example
Input
3
3
4
7
Output
1 3 2
1 4 2 3
1 7 2 3 4 5 6