CodeChef : September Challenge 2017 – Minimum Good Permutation

By | September 2, 2017

Minimum Good Permutation

Source: CodeChef

A permutation of length n is an array of size n consisting of n distinct integers in the range [1, n]. For example, (3, 2, 4, 1) is a permutation of length 4, but (3, 3, 1, 4) and (2, 3, 4, 5) are not, as (3, 3, 1, 4) contains duplicate elements, and (2, 3, 4, 5) contains elements not in range [1,4].

A permutation p of length n is good if and only if for any 1 ≤ i ≤ npi ≠ i.

Please find the lexicographically smallest good permutation p.

For two permutations p and q, we say that p is lexicographically smaller than q if and only if there exists a index 1 ≤ l ≤ n such that:

  • For any 1 ≤ i < lpi = qi. Note that if l = 1, this constraint means nothing.
  • and, pl < ql.

For example, (2, 3, 1, 4) < (2, 3, 4, 1) < (3, 4, 1, 2). The lexicographically smallest permutation is, of course, (1, 2, …, n), though this one is not good.

Input

First line of the input contains an integer T denoting number of test cases.

For each test case, the only line contains an integer n.

Output

For each test case, output the lexicographically smallest good permutation of length n. It’s guaranteed that this permutation exists.

Constraints

  • 1 ≤ T ≤ 10
  • 2 ≤ n ≤ 105

Subtasks

  • Subtask #1 (17 points)2 ≤ n ≤ 9
  • Subtask #2 (83 points): Original Constraints

Example

Input:
4
2
3
5
6

Output:
2 1
2 3 1
2 1 4 5 3
2 1 4 3 6 5

Explanation

Example case 1. The only good permutation of length 2 is (2, 1).

Example case 2. There are 2 good permutations of length 3: (2, 3, 1) and (3, 1, 2). The first one is lexicographically smaller.

Solution

Hint: I found it easier than the first one. Does not needs much of data Structure.