Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 4103
Traveler

Time Limit: 2 Seconds      Memory Limit: 65536 KB      Special Judge

The famous traveler BaoBao is visiting the Dream Kingdom now. There are $n$ cities in Dream Kingdom, numbered from $1$ to $n$. The cities are connected by directed roads. For all $1 \le i \le n$:

  • There is a road from the $i$-th city to the $(i-1)$-th city if $1 \le i-1 \le n$.
  • There is a road from the $i$-th city to the $2i$-th city if $1 \le 2i \le n$.
  • There is a road from the $i$-th city to the $(2i+1)$-th city if $1 \le 2i+1 \le n$.
  • There is a road from the $i$-th city to the $\lfloor \frac{i}{2} \rfloor$-th city if $1 \le \lfloor \frac{i}{2} \rfloor \le n$, where $\lfloor \frac{i}{2} \rfloor$ indicates the largest integer $x$ such that $2x \le i$.

BaoBao starts his travel from the 1st city. As he doesn't like visiting a city more than once, he wants to find a route which goes through each of the $n$ cities exactly once. Can you help him find such a route?

Input

There are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:

The first and the only line contains an integer $n$ ($1 \le n \le 10^5$), indicating the number of cities in Dream Kingdom.

It's guaranteed that the sum of $n$ of all test cases will not exceed $10^6$.

Output

For each test case output one line. If there exists a route which starts from the 1st city and visits each city exactly once, output $n$ integers $c_1, c_2, \dots, c_n$ separated by a space, where $c_i$ indicates the $i$-th city in the route (note that according to the description, there must be $c_1 = 1$). If there is no valid route, output "-1" (without quotes) instead. If there are multiple valid answers, you can output any of them.

Please, DO NOT output extra spaces at the end of each line, or your solution may be considered incorrect!

Sample Input

2
2
9

Sample Output

1 2
1 3 6 5 2 4 9 8 7

Author: CHEN, Shihan; WENG, Caizhi
Source: The 16th Zhejiang Provincial Collegiate Programming Contest Sponsored by TuSimple
Submit    Status