P5919 [POI 2004] MAK

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: $$p(p(\ldots(p(i))\ldots))=i$$ ($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

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 $d$ lines, each containing one optimal permutation.

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