A permutation of $n$ elements is a one-to-one function (injection) $π:\{1,2, \ldots ,n\} \mapsto \{1,2, \ldots ,n\}$. An order of permutation $π$ is the minimal $k \ge 1$, such that for all $i=1,2, \ldots ,n$ we have:
$$π(π(…(π(i))…))=i$$
i.e. $π$ composed with itself $k$ times becomes identity function. For example, the order of the permutation of $3$ elements $π(1)=3$, $π(2)=2$, $π(3)=1$ is $2$, because $π(π(1))=1$, $π(π(2))=2$, $π(π(3))=3$.
For a given $n$ let us consider permutations of $n$-elements having the the largest order possible. For example, the maximal order of a permutation of 5 elements is 6. An example of a permutation of 5 elements whose order is 6 is $π(1)=4$,$π(2)=5$,$π(3)=2$,$π(4)=1$,$π(5)=3$.
Among all permutations of $n$ elements having the maximal order, we would like to find the earliest one (in a lexicographical order). Being more precise, we say a permutation $π$ of $n$ elements is earlier than a permutation $σ$ of $n$ elements, if there exists $i$, such that $π(j)= σ(j)$ for all $j < i$ and $π(i) < σ(i)$. The earliest permutation of 5 elements having an order 6 is $π(1)=2$,$π(2)=1$,$π(3)=4$,$π(4)=5$,$π(5)=3$.
Task
Write a programme that:
- reads from the standard input a set of integers $n_1,n_2,\ldots,n_d$,
- for each number $n_i$ (for $i=1,2,\ldots ,d$) determines the earliest permutation of $n_i$ elements having the maximal order,
- writes the determined permutations to the standard output.
Input
There is one positive integer $d$ in the first line of the standard input, $1 \le d \le 10$. In the following $d$ lines there are positive integers $n_1,n_2,\ldots ,n_d$, one per line, $1 \le n_i \le 10\,000$.
Output
Your programme should write $d$ lines to the standard output. The $i$’th line should contain a sequence of integers separated by spaces, forming the least permutation of $n_i$ elements having the maximal order, i.e. the sequence $π(1),π(2),\ldots ,π(n_i)$, where $\pi$ denotes this permutation.
Example
Input
2 5 14
Output
2 1 4 5 3 2 3 1 5 6 7 4 9 10 11 12 13 14 8