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 CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
template <class T>
class vec : public vector<T> {
 public:
  void operator+=(vec<T> &b) { this->insert(this->end(), b.begin(), b.end()); }
  vec<T> operator+(vec<T> &b) {
    vec<T> c;
    for (T x : *this) c.push_back(x);
    for (T x : b) c.push_back(x);
    return c;
  }
  void operator+=(T &x) {
    for (int i = 0; i < this->size(); i++) {
      *this[i] += x;
    }
  }
  vec<T> operator+(T &x) {
    vec<T> c;
    for (auto y : *this) {
      c.push_back(x + y);
    }
    return c;
  }
  void operator-=(vec<T> &b) {
    for (auto x : b) {
      this->pop_back();
    }
  }
  void operator-(vec<T> &b) {
    vec<T> a = *this;
    for (auto x : b) {
      a.pop_back();
    }
    return a;
  }
};
struct rll {
  long long MAX = LLONG_MAX - 7;
  long long val;
  rll(long long x = 0) : val(x) {}
  rll operator+(rll b) {
    if (val >= MAX - b.val) {
      return rll(MAX);
    }
    return rll(val + b.val);
  }
  rll operator*(rll b) {
    if (val >= MAX / b.val) {
      return rll(MAX);
    }
    return rll(val * b.val);
  }
  operator long long() { return val; }
  bool operator==(int x) { return val == x; }
  bool operator==(long long x) { return val == x; }
  bool operator==(rll b) { return val == b.val; }
};
rll dp[55], dpfact[55];
rll fact(long long n) {
  if (dpfact[n] == -1) {
    if (n <= 1) return 1;
    dpfact[n] = n * fact(n - 1);
  }
  return dpfact[n];
}
rll combinations(long long n) {
  if (n < 3) return fact(1);
  return fact(n + (-2));
}
vec<vec<long long> > allGoodPermutations;
long long rv[55];
void trans(long long num, long long n, int cnt = 0) {
  if (cnt == n) {
    vec<long long> goodPermutation;
    for (int i = 1; i <= n; i++) goodPermutation.push_back(rv[i]);
    allGoodPermutations.push_back(goodPermutation);
    return;
  }
  if (cnt == 0) {
    rv[1] = num;
    trans(1, n, cnt + 1);
    rv[1] = 0;
    return;
  }
  if (cnt == n - 1) {
    rv[n] = num;
    trans(n, n, cnt + 1);
    rv[n] = 0;
    return;
  }
  for (int i = 2; i < n; i++) {
    if (rv[i] == 0) {
      rv[i] = num;
      trans(i, n, cnt + 1);
      rv[i] = 0;
    }
  }
}
rll rec(long long n) {
  if (dp[n] == -1) {
    if (n <= 1) {
      dp[n] = 1;
    } else {
      dp[n] = combinations(n);
      for (long long i = 1; i < n; i++) {
        dp[n] = dp[n] + combinations(i) * rec(n - i);
      }
    }
  }
  return dp[n];
}
vec<pair<long long, long long> > sol;
void analyze(rll n, rll k) {
  if (k == 0) {
    assert(n == 0);
    return;
  }
  if (n == 1 && k == 1) {
    sol.push_back({1, 1});
    return;
  }
  for (int i = 1; i <= n; i++) {
    if (rec(n - i) * combinations(i) < k) {
      k = k - rec(n - i) * combinations(i);
    } else {
      long long restCombinations = rec(n - i);
      long long cycleNumber = (long long)k / restCombinations;
      if ((restCombinations * cycleNumber) < k) {
        k = k - restCombinations * cycleNumber;
        cycleNumber++;
      } else {
        k = k - restCombinations * (cycleNumber - 1);
      }
      sol.push_back({i, cycleNumber});
      analyze(n - i, k);
      break;
    }
  }
}
long long arr[55], mark[55];
vec<long long> solution;
bool isvalid(int n, int position = 1, int cnt = 0) {
  if (position == 1) {
    if (cnt == n) return true;
    if (cnt != 0) return false;
  }
  if (cnt == n) return false;
  return isvalid(n, arr[position], cnt + 1);
}
bool isConflict(long long pos, long long num) {
  if (mark[num]) return true;
  if (num == pos) return true;
  bool loop = false;
  long long tmp = num;
  while (arr[tmp] != 0) {
    tmp = arr[tmp];
    if (tmp == pos) loop = true;
  }
  return loop;
}
void kth_trans(long long n, long long k, long long start = 1) {
  if (n == 1) {
    solution.push_back(start);
    return;
  }
  if (n == 2) {
    solution.push_back(start + 1);
    solution.push_back(start);
    return;
  }
  if (n == 3) {
    solution.push_back(start + 2);
    solution.push_back(start);
    solution.push_back(start + 1);
    return;
  }
  arr[1] = n;
  mark[n] = 1;
  solution.push_back(n + start - 1);
  for (int i = 2; i <= n - 3; i++) {
    rll left = n - i - 1;
    rll possibleCombinationsforEachNumber = fact(left);
    long long whichNumber = k / possibleCombinationsforEachNumber;
    if (whichNumber * possibleCombinationsforEachNumber < k) whichNumber++;
    k = k % possibleCombinationsforEachNumber;
    if (k == 0) k = possibleCombinationsforEachNumber;
    for (int j = 1; j <= n; j++) {
      if (isConflict(i, j)) continue;
      whichNumber--;
      if (whichNumber == 0) {
        arr[i] = j;
        mark[j] = 1;
        break;
      }
    }
    solution.push_back(start + arr[i] - 1);
  }
  vec<long long> unmarked;
  for (int i = 1; i <= n; i++) {
    if (mark[i]) continue;
    unmarked.push_back(i);
  }
  for (int i = 0; i < 3; i++) {
    for (int j = 0; j < 3; j++) {
      if (i == j) continue;
      for (int k2 = 0; k2 < 3; k2++) {
        if (j == k2) continue;
        arr[n - 2] = unmarked[i];
        arr[n - 1] = unmarked[j];
        arr[n] = unmarked[k2];
        if (isvalid(n)) k--;
        if (k == 0) {
          solution.push_back(start + arr[n - 2] - 1);
          solution.push_back(start + arr[n - 1] - 1);
          solution.push_back(start + arr[n] - 1);
          return;
        }
      }
    }
  }
}
int main() {
  for (int i = 0; i < 55; i++) {
    dp[i] = -1;
    dpfact[i] = -1;
  }
  int t;
  cin >> t;
  while (t--) {
    long long n, k;
    cin >> n >> k;
    long long total_possible = rec(n);
    if (total_possible < k) {
      cout << -1 << endl;
      continue;
    }
    sol.clear();
    analyze(n, k);
    solution.clear();
    long long start = 1;
    for (auto s : sol) {
      memset(arr, 0, sizeof arr);
      memset(mark, 0, sizeof mark);
      kth_trans(s.first, s.second, start);
      start += s.first;
    }
    for (auto x : solution) {
      cout << x << " ";
    }
    cout << endl;
  }
  return 0;
}