순열의 최대 위수

$n$개의 원소로 이루어진 순열은 전단사 함수 $\pi:\{1,2,\dots,n\}\to\{1,2,\dots,n\}$이다.

순열 $\pi$의 위수(order) 는 다음을 만족하는 가장 작은 정수 $k\ge 1$이다. 모든 $i=1,2,\dots,n$에 대해

$\underbrace{\pi(\pi(\cdots\pi(i)\cdots))}_{k\text{번}} = i,$

즉 $\pi$를 자기 자신과 $k$번 합성하면 항등함수가 된다. 예를 들어 $n=3$일 때 순열 $\pi(1)=3,\ \pi(2)=2,\ \pi(3)=1$의 위수는 $2$인데, 모든 $i$에 대해 $\pi(\pi(i))=i$이기 때문이다.

주어진 $n$에 대해, 위수가 가능한 한 큰 순열들을 생각하자. 예를 들어 $5$개 원소의 순열 중 최대 위수는 $6$이며, 위수가 $6$인 순열의 한 예는 $\pi(1)=4,\ \pi(2)=5,\ \pi(3)=2,\ \pi(4)=1,\ \pi(5)=3$이다.

최대 위수를 가지는 $n$개 원소의 순열들 중에서 사전순으로 가장 앞서는(가장 작은) 것을 찾고자 한다. 엄밀히 말해, 순열 $\pi$가 순열 $\sigma$보다 앞선다는 것은 어떤 첨자 $i$가 존재하여 모든 $j<i$에 대해 $\pi(j)=\sigma(j)$이고 $\pi(i)<\sigma(i)$인 경우를 뜻한다. $n=5$일 때 위수가 $6$인 순열 중 사전순으로 가장 작은 것은 $\pi(1)=2,\ \pi(2)=1,\ \pi(3)=4,\ \pi(4)=5,\ \pi(5)=3$이다.

여러 개의 값 $n_1,n_2,\dots,n_d$를 입력받아, 각 $n_i$에 대해 위수가 최대인 $n_i$개 원소의 순열 중 사전순으로 가장 작은 것을 출력하는 프로그램을 작성하라.

첫째 줄에 정수 $d$가 주어진다 ($1\le d\le 10$). 이어지는 $d$개의 줄에는 각각 하나의 정수 $n_i$가 주어진다 ($1\le n_i\le 10000$).

$d$개의 줄을 출력한다. $i$번째 줄에는 위수가 최대인 $n_i$개 원소의 순열 중 사전순으로 가장 작은 것, 즉 수열 $\pi(1),\pi(2),\dots,\pi(n_i)$를 공백 하나로 구분하여 출력한다.