C1. Yet Another Nim Game (Constructive version)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice and Bob decided to play the following game on $$$n$$$ piles of stones where the $$$i$$$-th$$$(1 \le i \le n)$$$ pile contains $$$p_i$$$ stones with Alice starting first :

  • On his/her turn, he/she will choose any $$$k(1 \le k \le n)$$$ distinct arbitrary piles which have a positive number of stones(note that $$$k$$$ can be chosen arbitrarily by the current player). Now the player will remove exactly one stone each from all selected $$$k$$$ piles.

The player who cannot make a move loses. Note that both Alice and Bob are intelligent, so they always play optimally.

Now your task is to construct any permutation$$$^\dagger$$$ $$$p$$$ of length $$$n$$$ such that the number of pairs ($$$l, r$$$)($$$1 \le l \le r \le n$$$), where Alice will win if both players play the game on piles $$$l, l+1, ..., r-1, r$$$, is maximum possible.

$$$^\dagger$$$ A permutation is an array of length $$$n$$$, where each number from $$$1$$$ to $$$n$$$ appears exactly once.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10000$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — the number of piles.

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$3 \cdot 10^5$$$.

Output

For each test case, print $$$n$$$ integers — the required permutation $$$p$$$.

If there are multiple answers, output any.

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