Problem Description

A permutation is a one-to-one function mapping of $n$ elements $p:\{1,2,\ldots,n\}\to\{1,2,\ldots,n\}$. The order of a permutation $p$ is the smallest $k\ge 1$ such that for all $i=1,2,\ldots,n$, the following holds:

($k$ times in total).

For example, for $3$ elements, the permutation with order $2$ is $p(1)=3,p(2)=2,p(3)=1$, because $p(p(1))=1,p(p(2))=2,p(p(3))=3$.

For a given $n$, we want a permutation of length $n$ whose order is as large as possible. For example, among permutations of length $5$, the maximum possible order is $6$.

One example is $p(1)=4,p(2)=5,p(3)=2,p(4)=1,p(5)=3$.

Among all permutations that achieve the maximum order, we need to find the lexicographically smallest one.

More precisely, we say permutation $p$ is smaller than permutation $r$ if there exists an $i$ such that for all $j<i$ we have $p(j)=r(j)$ and $p(i)<r(i)$. Then, among permutations of length $5$, the smallest one is $p(1)=2,p(2)=1,p(3)=4,p(4)=5,p(5)=3$.

Input Format

The first line contains an integer $d$, meaning there are $d$ test cases.

The next $d$ lines give the lengths $n_1,n_2,\ldots,n_d$.

Output Format

Output $d$ lines, each containing one optimal permutation.

2
5
14

2 1 4 5 3
2 3 1 5 6 7 4 9 10 11 12 13 14 8

Hint

For $100\%$ of the testdata, $1\le d\le 10$ and $1\le n_i\le 10^4$.

Translated by ChatGPT 5