K. Derangements
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given two integers $$$n$$$ and $$$k$$$, your task is to find the $$$k$$$-th smallest derangement$$$^{[4]}$$$ of length $$$n$$$ when all derangements of length $$$n$$$ are listed in lexicographical order$$$^{[2]}$$$.

Input

The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 2000$$$) — the number of testcases.

The first line of each testcase contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 10^5$$$, $$$1 \le k \le 10^{15}$$$).

It is guaranteed that there are at least $$$k$$$ derangements of length $$$n$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output

For each test case, output a single line containing $$$n$$$ integers $$$p_1, p_2, \ldots, p_n$$$ — the $$$k$$$-th smallest derangement of length $$$n$$$.

Example
Input
4
2 1
3 1
3 2
4 6
Output
2 1 
2 3 1 
3 1 2 
3 4 2 1
Note

In the fourth test case, below is the list of all derangements of length $$$4$$$ in lexicographical order:

$$$$$$[2, 1, 4, 3] , [2, 3, 4, 1] , [2, 4, 1, 3] , [3, 1, 4, 2] , [3, 4, 1, 2] , [3, 4, 2, 1] , [4, 1, 2, 3] , [4, 3, 1, 2] , [4, 3, 2, 1]$$$$$$

Thus, the $$$6$$$-th smallest derangement of length $$$4$$$ is $$$[3, 4, 2, 1]$$$.