COMBINATORICS

Use cpp for the answer

Description

Switch adjacent is an order to list all n-permutations. In switch adjacent order, each permutation is obtained from the preceding one by switching two adjacent numbers. For example, switch adjacent order for 3-permutation is 1 2 3, 1 3 2, 3 1 2, 3 2 1, 2 3 1, 2 1 3.

Given positive integers n and k, output the kth permutation in switch adjacent order. For example,let n = 3, k=2, the answer is 1 3 2.

Input The first row is a positive integer m, which is the number of test cases. It is followed by m test cases. Each test case has one line with two positive integers n( 1 <= n < 12 ) and k(1<=k<=n!)

Output For each test case, output one line with an n-permutation, i.e., n numbers valued from 1 to n, which is the kth n-permutation in switch adjacent order.

Sample input

3 3 1 3 6 10 100

Sample output

1 2 3

2 1 3

9 1 2 3 4 5 6 8 7 10

NOTE:

OUTPUT FOR 10 100 must be 9 1 2 3 4 5 6 8 7 10 and not 10 9 1 2 3 4 5 6 8 7

ExplainFor input 10 100, the output is 9 1 2 3 4 5 6 8 7 10.