Problem: Yeah, we failed to make up a New Year legend for this problem.

A permutation of length n is an array of n integers such that every integer from 1 to n appears in it exactly once. 

An element y of permutation p is reachable from element x if x = y, or p_x = y, or p_{p_x} = y, and so on. 

The decomposition of a permutation p is defined as follows: firstly, we have a permutation p, all elements of which are not marked, and an empty list l. Then we do the following: while there is at least one not marked element in p, we find the leftmost such element, list all elements that are reachable from it in the order they appear in p, mark all of these elements, then cyclically shift the list of those elements so that the maximum appears at the first position, and add this list as an element of l. After all elements are marked, l is the result of this decomposition.

For example, if we want to build a decomposition of p = [5, 4, 2, 3, 1, 7, 8, 6], we do the following:

  1. initially p = [5, 4, 2, 3, 1, 7, 8, 6] (bold elements are marked), l = []; 
  2. the leftmost unmarked element is 5; 5 and 1 are reachable from it, so the list we want to shift is [5, 1]; there is no need to shift it, since maximum is already the first element; 
  3. p = [5, 4, 2, 3, 1, 7, 8, 6], l = [[5, 1]]; 
  4. the leftmost unmarked element is 4, the list of reachable elements is [4, 2, 3]; the maximum is already the first element, so there's no need to shift it; 
  5. p = [5, 4, 2, 3, 1, 7, 8, 6], l = [[5, 1], [4, 2, 3]]; 
  6. the leftmost unmarked element is 7, the list of reachable elements is [7, 8, 6]; we have to shift it, so it becomes [8, 6, 7]; 
  7. p = [5, 4, 2, 3, 1, 7, 8, 6], l = [[5, 1], [4, 2, 3], [8, 6, 7]]; 
  8. all elements are marked, so [[5, 1], [4, 2, 3], [8, 6, 7]] is the result. 



The New Year transformation of a permutation is defined as follows: we build the decomposition of this permutation; then we sort all lists in decomposition in ascending order of the first elements (we don't swap the elements in these lists, only the lists themselves); then we concatenate the lists into one list which becomes a new permutation. For example, the New Year transformation of p = [5, 4, 2, 3, 1, 7, 8, 6] is built as follows:

  1. the decomposition is [[5, 1], [4, 2, 3], [8, 6, 7]]; 
  2. after sorting the decomposition, it becomes [[4, 2, 3], [5, 1], [8, 6, 7]]; 
  3. [4, 2, 3, 5, 1, 8, 6, 7] is the result of the transformation. 



We call a permutation good if the result of its transformation is the same as the permutation itself. For example, [4, 3, 1, 2, 8, 5, 6, 7] is a good permutation; and [5, 4, 2, 3, 1, 7, 8, 6] is bad, since the result of transformation is [4, 2, 3, 5, 1, 8, 6, 7].

Your task is the following: given n and k, find the k-th (lexicographically) good permutation of length n.

Input

The first line contains one integer t (1 ≤ t ≤ 1000) — the number of test cases.

Then the test cases follow. Each test case is represented by one line containing two integers n and k (1 ≤ n ≤ 50, 1 ≤ k ≤ 10^{18}).

Output

For each test case, print the answer to it as follows: if the number of good permutations of length n is less than k, print one integer -1; otherwise, print the k-th good permutation on n elements (in lexicographical order).

Example

Input


5
3 3
5 15
4 13
6 8
4 2


Output


2 1 3 
3 1 2 5 4 
-1
1 2 6 3 4 5 
1 2 4 3 

Solution (in JAVA):

Solution:
import java.io.*;
import java.util.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

// editorial: lexicographic recovery
// https://codeforces.com/blog/entry/72577

public class cf1279e {

    public static void main(String[] args) throws IOException {
        int t = ri();
        // int t = 1000;
        long fact[] = new long[49], cyc[] = new long[51], inf = (long) 2e18;
        fact[0] = fact[1] = cyc[0] = cyc[1] = 1;
        for (int i = 2; i <= 20; ++i) {
            fact[i] = i * fact[i - 1];
        }
        // 20! ~= 2e18
        for (int i = 21; i <= 48; ++i) {
            fact[i] = fact[i - 1];
        }
        for (int i = 2; i <= 50; ++i) {
            cyc[i] = fact[i - 2];
        }
        while (t --> 0) {
            int n = rni(), ans[] = new int[n];
            long k = nl() - 1;
            // int n = 8, k = 618 + (1000 - t), ans[] = new int[n];
            fill(ans, -1);
            boolean[] used = new boolean[n];
            long dp[] = new long[n + 1];
            dp[n] = 1;
            for (int i = n - 1; i >= 0; --i) {
                double check = 0;
                for (int j = i; j < n; ++j) {
                    dp[i] += dp[j + 1] * cyc[j - i + 1];
                    check += (double) dp[j + 1] * cyc[j - i + 1];
                }
                if (check > inf) {
                    dp[i] = inf;
                }
            }
            // prln(k);
            if (dp[0] <= k) {
                prln(-1);
                flush();
                continue;
            }
            for (int i = 0; i < n; ++i) {
                for (int j = i; j < n; ++j) {
                    long block = (double) dp[j + 1] * cyc[j - i + 1] > inf ? inf : dp[j + 1] * cyc[j - i + 1];
                    if (block <= k) {
                        // skip this block
                        k -= block;
                        continue;
                    }
                    ans[i] = j;
                    used[j] = true;
                    for (int l = i + 1; l <= j; ++l) {
                        int left = j - l;
                        for (int x = i; x < j; ++x) {
                            // if not used and is not fixed point
                            if (!used[x] && l != x) {
                                // if not last one in block
                                if (l != j) {
                                    // must not form a cycle
                                    int buf = ans[x];
                                    while (buf != -1 && buf != l) {
                                        buf = ans[buf];
                                    }
                                    if (buf == l) {
                                        // forms a cycle
                                        continue;
                                    }
                                }
                                block = (double) dp[j + 1] * cyc[left + 1] > inf ? inf : dp[j + 1] * cyc[left + 1];
                                if (block <= k) {
                                    k -= block;
                                    continue;
                                }
                                ans[l] = x;
                                used[x] = true;
                                break;
                            }
                        }
                    }
                    // block finished
                    i = j;
                    break;
                }
            }
            for (int i = 0; i < n; ++i) {
                ++ans[i];
            }
            prln(ans);
            flush();
        }
        close();
    }

    static BufferedReader __in = new BufferedReader(new InputStreamReader(System.in));
    static PrintWriter __out = new PrintWriter(new OutputStreamWriter(System.out));
    static StringTokenizer input;
    static Random __rand = new Random();

    // references
    // IBIG = 1e9 + 7
    // IMAX ~= 2e10
    // LMAX ~= 9e18
    
    // constants
    static final int IBIG = 1000000007;
    static final int IMAX = 2147483647;
    static final int IMIN = -2147483648;
    static final long LMAX = 9223372036854775807L;
    static final long LMIN = -9223372036854775808L;
    // math util
    static int minof(int a, int b, int c) {return min(a, min(b, c));}
    static int minof(int... x) {if(x.length == 1) return x[0]; if(x.length == 2) return min(x[0], x[1]); if(x.length == 3) return min(x[0], min(x[1], x[2])); int min = x[0]; for(int i = 1; i < x.length; ++i) if(x[i] < min) min = x[i]; return min;}
    static long minof(long a, long b, long c) {return min(a, min(b, c));}
    static long minof(long... x) {if(x.length == 1) return x[0]; if(x.length == 2) return min(x[0], x[1]); if(x.length == 3) return min(x[0], min(x[1], x[2])); long min = x[0]; for(int i = 1; i < x.length; ++i) if(x[i] < min) min = x[i]; return min;}
    static int maxof(int a, int b, int c) {return max(a, max(b, c));}
    static int maxof(int... x) {if(x.length == 1) return x[0]; if(x.length == 2) return max(x[0], x[1]); if(x.length == 3) return max(x[0], max(x[1], x[2])); int max = x[0]; for(int i = 1; i < x.length; ++i) if(x[i] > max) max = x[i]; return max;}
    static long maxof(long a, long b, long c) {return max(a, max(b, c));}
    static long maxof(long... x) {if(x.length == 1) return x[0]; if(x.length == 2) return max(x[0], x[1]); if(x.length == 3) return max(x[0], max(x[1], x[2])); long max = x[0]; for(int i = 1; i < x.length; ++i) if(x[i] > max) max = x[i]; return max;}
    static int powi(int a, int b) {if(a == 0) return 0; int ans = 1; while(b > 0) {if((b & 1) > 0) ans *= a; a *= a; b >>= 1;} return ans;}
    static long powl(long a, int b) {if(a == 0) return 0; long ans = 1; while(b > 0) {if((b & 1) > 0) ans *= a; a *= a; b >>= 1;} return ans;}
    static int fli(double d) {return (int)d;}
    static int cei(double d) {return (int)ceil(d);}
    static long fll(double d) {return (long)d;}
    static long cel(double d) {return (long)ceil(d);}
    static int gcf(int a, int b) {return b == 0 ? a : gcf(b, a % b);}
    static long gcf(long a, long b) {return b == 0 ? a : gcf(b, a % b);}
    static int randInt(int min, int max) {return __rand.nextInt(max - min + 1) + min;}
    static long hash(long x) {x += 0x9e3779b97f4a7c15L; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9L; x = (x ^ (x >> 27)) * 0x94d049bb133111ebL; return x ^ (x >> 31);}
    // array util
    static void reverse(int[] a) {for(int i = 0, n = a.length, half = n / 2; i < half; ++i) {int swap = a[i]; a[i] = a[n - i - 1]; a[n - i - 1] = swap;}}
    static void reverse(long[] a) {for(int i = 0, n = a.length, half = n / 2; i < half; ++i) {long swap = a[i]; a[i] = a[n - i - 1]; a[n - i - 1] = swap;}}
    static void reverse(char[] a) {for(int i = 0, n = a.length, half = n / 2; i < half; ++i) {char swap = a[i]; a[i] = a[n - i - 1]; a[n - i - 1] = swap;}}
    static void shuffle(int[] a) {int n = a.length - 1; for(int i = 0; i < n; ++i) {int ind = randInt(i, n); int swap = a[i]; a[i] = a[ind]; a[ind] = swap;}}
    static void shuffle(long[] a) {int n = a.length - 1; for(int i = 0; i < n; ++i) {int ind = randInt(i, n); long swap = a[i]; a[i] = a[ind]; a[ind] = swap;}}
    static void rsort(int[] a) {shuffle(a); sort(a);}
    static void rsort(long[] a) {shuffle(a); sort(a);}
    static int[] copy(int[] a) {int[] ans = new int[a.length]; for(int i = 0; i < a.length; ++i) ans[i] = a[i]; return ans;}
    static long[] copy(long[] a) {long[] ans = new long[a.length]; for(int i = 0; i < a.length; ++i) ans[i] = a[i]; return ans;}
    static char[] copy(char[] a) {char[] ans = new char[a.length]; for(int i = 0; i < a.length; ++i) ans[i] = a[i]; return ans;}
    static int[] sorted(int[] a) {int[] ans = copy(a); sort(ans); return ans;}
    static long[] sorted(long[] a) {long[] ans = copy(a); sort(ans); return ans;}
    static int[] rsorted(int[] a) {int[] ans = copy(a); rsort(ans); return ans;}
    static long[] rsorted(long[] a) {long[] ans = copy(a); rsort(ans); return ans;}
    // graph util
    static List<List<Integer>> graph(int n) {List<List<Integer>> g = new ArrayList<>(); for(int i = 0; i < n; ++i) g.add(new ArrayList<>()); return g;}
    static List<List<Integer>> graph(List<List<Integer>> g, int m) throws IOException {for(int i = 0; i < m; ++i) connect(g, rni() - 1, ni() - 1); return g;}
    static List<List<Integer>> graph(int n, int m) throws IOException {return graph(graph(n), m);}
    static List<List<Integer>> dgraph(List<List<Integer>> g, int m) throws IOException {for(int i = 0; i < m; ++i) connecto(g, rni() - 1, ni() - 1); return g;}
    static List<List<Integer>> dgraph(List<List<Integer>> g, int n, int m) throws IOException {return dgraph(graph(n), m);}
    static List<Set<Integer>> sgraph(int n) {List<Set<Integer>> g = new ArrayList<>(); for(int i = 0; i < n; ++i) g.add(new HashSet<>()); return g;}
    static List<Set<Integer>> sgraph(List<Set<Integer>> g, int m) throws IOException {for(int i = 0; i < m; ++i) connect(g, rni() - 1, ni() - 1); return g;}
    static List<Set<Integer>> sgraph(int n, int m) throws IOException {return sgraph(sgraph(n), m);}
    static List<Set<Integer>> dsgraph(List<Set<Integer>> g, int m) throws IOException {for(int i = 0; i < m; ++i) connecto(g, rni() - 1, ni() - 1); return g;}
    static List<Set<Integer>> dsgraph(List<Set<Integer>> g, int n, int m) throws IOException {return dsgraph(sgraph(n), m);}
    static void connect(List<? extends Collection<Integer>> g, int u, int v) {g.get(u).add(v); g.get(v).add(u);}
    static void connecto(List<? extends Collection<Integer>> g, int u, int v) {g.get(u).add(v);}
    static void dconnect(List<? extends Collection<Integer>> g, int u, int v) {g.get(u).remove(v); g.get(v).remove(u);}
    static void dconnecto(List<? extends Collection<Integer>> g, int u, int v) {g.get(u).remove(v);}
    // input
    static void r() throws IOException {input = new StringTokenizer(__in.readLine());}
    static int ri() throws IOException {return Integer.parseInt(__in.readLine());}
    static long rl() throws IOException {return Long.parseLong(__in.readLine());}
    static int[] ria(int n) throws IOException {int[] a = new int[n]; input = new StringTokenizer(__in.readLine()); for(int i = 0; i < n; ++i) a[i] = Integer.parseInt(input.nextToken()); return a;}
    static int[] riam1(int n) throws IOException {int[] a = new int[n]; input = new StringTokenizer(__in.readLine()); for(int i = 0; i < n; ++i) a[i] = Integer.parseInt(input.nextToken()) - 1; return a;}
    static long[] rla(int n) throws IOException {long[] a = new long[n]; input = new StringTokenizer(__in.readLine()); for(int i = 0; i < n; ++i) a[i] = Long.parseLong(input.nextToken()); return a;}
    static char[] rcha() throws IOException {return __in.readLine().toCharArray();}
    static String rline() throws IOException {return __in.readLine();}
    static int rni() throws IOException {input = new StringTokenizer(__in.readLine()); return Integer.parseInt(input.nextToken());}
    static int ni() {return Integer.parseInt(input.nextToken());}
    static long rnl() throws IOException {input = new StringTokenizer(__in.readLine()); return Long.parseLong(input.nextToken());}
    static long nl() {return Long.parseLong(input.nextToken());}
    // output
    static void pr(int i) {__out.print(i);}
    static void prln(int i) {__out.println(i);}
    static void pr(long l) {__out.print(l);}
    static void prln(long l) {__out.println(l);}
    static void pr(double d) {__out.print(d);}
    static void prln(double d) {__out.println(d);}
    static void pr(char c) {__out.print(c);}
    static void prln(char c) {__out.println(c);}
    static void pr(char[] s) {__out.print(new String(s));}
    static void prln(char[] s) {__out.println(new String(s));}
    static void pr(String s) {__out.print(s);}
    static void prln(String s) {__out.println(s);}
    static void pr(Object o) {__out.print(o);}
    static void prln(Object o) {__out.println(o);}
    static void prln() {__out.println();}
    static void pryes() {__out.println("yes");}
    static void pry() {__out.println("Yes");}
    static void prY() {__out.println("YES");}
    static void prno() {__out.println("no");}
    static void prn() {__out.println("No");}
    static void prN() {__out.println("NO");}
    static void pryesno(boolean b) {__out.println(b ? "yes" : "no");};
    static void pryn(boolean b) {__out.println(b ? "Yes" : "No");}
    static void prYN(boolean b) {__out.println(b ? "YES" : "NO");}
    static void prln(int... a) {for(int i = 0, len = a.length - 1; i < len; __out.print(a[i]), __out.print(' '), ++i); __out.println(a[a.length - 1]);}
    static void prln(long... a) {for(int i = 0, len = a.length - 1; i < len; __out.print(a[i]), __out.print(' '), ++i); __out.println(a[a.length - 1]);}
    static <T> void prln(Collection<T> c) {int n = c.size() - 1; Iterator<T> iter = c.iterator(); for(int i = 0; i < n; __out.print(iter.next()), __out.print(' '), ++i); if(n >= 0) __out.println(iter.next()); else __out.println();}
    static void h() {__out.println("hlfd");}
    static void flush() {__out.flush();}
    static void close() {__out.close();}
}