Permutation Construction with Exact Number of Increasing Subsequences

You are given a number k, which represents the exact number of increasing subsequences that can be chosen from a permutation p of length n. The permutation p is a rearrangement of the integers from 0 to n-1 and is used to model orbital speeds of planets. When a spaceship flies by each planet in the order p[0], p[1], …, p[n - 1], scientists can choose whether or not to use that planet for a gravity assist. However, to save energy, if the spaceship accelerates using planet i with speed p[i], it cannot accelerate at a later planet j if p[j] < p[i]. In other words, the planets chosen for acceleration must form an increasing subsequence of p.

It is known that there are exactly k ways to select the accelerating planets (note that the empty subsequence is considered valid). Moreover, the scientists recall that p is a permutation of 0, 1, …, n-1 (each integer appears exactly once). Your task is to construct such a permutation with n as small as possible so that the total number of increasing subsequences equals k (where an increasing subsequence is defined over the positions in p and the empty subsequence is counted).

Key Observation:

If the permutation is divided into several contiguous blocks, and if the numbers in each block (when arranged in decreasing order) are all less than the numbers in later blocks, then any increasing subsequence can pick at most one element from each block. In such a structure, if a block has size b, there are (b + 1) choices (either choosing nothing or one of its b elements) from that block. Hence, the total number of increasing subsequences is given by:

$$ \prod_{i=1}^{m} (b_i+1)=k, $$

where the permutation is divided into m blocks with block sizes b_1, b_2, \dots, b_m.

Our construction strategy is as follows:

1. Factorize k into a product of integers each at least 2. In an optimal construction, we completely factorize k into prime factors. For every prime factor p, we use a block of size (p - 1) (since (b+1)=p gives b=p-1).
2. The overall permutation size will be n = \sum (p-1) over all factors.
3. Assign the smallest n numbers (i.e. 0 to n-1) to the blocks in increasing order. For each block, output the numbers in decreasing order.

This guarantees that all elements in an earlier block are smaller than any element in a later block, and within each block, because the order is decreasing, you cannot pick two elements and have an increasing sequence. Thus, any increasing subsequence picks at most one element per block, and the total count is exactly k.

inputFormat

The input begins with an integer q (q > 0), indicating the number of spaceships (test cases). Each of the next q lines contains a single integer k (k ≥ 2), which is the exact number of increasing subsequences (including the empty subsequence) that should be formed from the permutation.

Note: It is guaranteed that a valid permutation exists for the given k, and you must construct one with the minimal possible length n.

outputFormat

For each test case, output a single line containing the constructed permutation of n space-separated integers (which are a permutation of 0, 1, …, n-1) that yields exactly k increasing subsequences.

sample

1
2

0