Maximal Orders of Permutations

A permutation of $n$ elements is a bijection $\pi:\{1,2,\dots,n\}\to\{1,2,\dots,n\}$.

The order of a permutation $\pi$ is the smallest integer $k\ge 1$ such that applying $\pi$ to every element $k$ times returns each element to itself:

$\underbrace{\pi(\pi(\cdots\pi(i)\cdots))}_{k\text{ times}} = i \quad\text{for all } i=1,2,\dots,n,$

that is, $\pi$ composed with itself $k$ times is the identity. For example, for $n=3$ the permutation $\pi(1)=3,\ \pi(2)=2,\ \pi(3)=1$ has order $2$, because $\pi(\pi(i))=i$ for every $i$.

For a given $n$, consider the permutations of $n$ elements whose order is as large as possible. For instance, the maximal order over all permutations of $5$ elements is $6$; one permutation of $5$ elements with order $6$ is $\pi(1)=4,\ \pi(2)=5,\ \pi(3)=2,\ \pi(4)=1,\ \pi(5)=3$.

Among all permutations of $n$ elements that attain this maximal order, we want the lexicographically smallest one. Formally, a permutation $\pi$ is earlier than a permutation $\sigma$ if there is an index $i$ with $\pi(j)=\sigma(j)$ for all $j<i$ and $\pi(i)<\sigma(i)$. For $n=5$, the lexicographically smallest permutation of order $6$ is $\pi(1)=2,\ \pi(2)=1,\ \pi(3)=4,\ \pi(4)=5,\ \pi(5)=3$.

Write a program that reads several values $n_1,n_2,\dots,n_d$ and, for each $n_i$, outputs the lexicographically smallest permutation of $n_i$ elements whose order is maximal.

The first line contains a single integer $d$ ($1\le d\le 10$). Each of the next $d$ lines contains one integer $n_i$ ($1\le n_i\le 10000$).

Print $d$ lines. The $i$-th line must contain the sequence $\pi(1),\pi(2),\dots,\pi(n_i)$ — the lexicographically smallest permutation of $n_i$ elements whose order is maximal — with the numbers separated by single spaces.