Print all permutations of n distinct symbols using the Johnson-Trotter algorithm.

Input

Input begins with t (1 ≤ t ≤ 9) of number of test-cases in the first line and a test-case in each of the following lines. A test-case has a positive integer n (1 ≤ n ≤ 9) in a single line.

Output

For each test-case, print all the permutations one per line in the order of generation of permutations by the Johnson-Trotter algorithm. A permutation is symbols from 1 to n separated by a space.

Example

Input:
3
1
2
3

Output:
1
1 2
2 1
1 2 3
1 3 2
3 1 2
3 2 1
2 3 1
2 1 3