Given a number N, you have to print all possible N–digit numbers such that all the digits of every number are distinct, non-zero and at most N. Note that these numbers must be printed in ascending order.

Input

First line consists of T, the number of test cases. The next T lines are such that each line consists of a single integer N.

Output

For every test case print all the numbers as mentioned above, each number being separated by a single space. Print the answer to each test case on a new line.

Constraints

1 <= T <= 3
1 <= N <= 9