#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vvvl = vector<vvl>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vvvb = vector<vvb>;
using vc = vector<char>;
using vvc = vector<vc>;
using vvvc = vector<vvc>;
using vd = vector<double>;
using vvd = vector<vd>;
using vvvd = vector<vvd>;
template <class T>
using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>;
using Graph = vvi;
const double PI = 3.14159265359;
const double DEG = PI / 180.;
const vi dx4 = {1, 0, -1, 0};
const vi dy4 = {0, 1, 0, -1};
const vi dx8 = {1, 1, 0, -1, -1, -1, 0, 1};
const vi dy8 = {0, 1, 1, 1, 0, -1, -1, -1};
const int INF = 1001001001;
const ll INFL = 2002002002002002002LL;
const double EPS = 1e-10;
struct fast_io {
  fast_io() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
  }
} fast_io_tmp;
template <class T>
inline ll pow(T n, int k) {
  ll v = 1;
  for (int i = 0, i_len = int(k); i < i_len; ++i) v *= n;
  return v;
}
template <class T>
inline bool chmax(T& M, const T& x) {
  if (M < x) {
    M = x;
    return true;
  }
  return false;
}
template <class T>
inline bool chmin(T& m, const T& x) {
  if (m > x) {
    m = x;
    return true;
  }
  return false;
}
template <class T, class U>
inline istream& operator>>(istream& is, pair<T, U>& p) {
  is >> p.first >> p.second;
  return is;
}
template <class T, class U>
inline ostream& operator<<(ostream& os, const pair<T, U>& p) {
  os << "(" << p.first << "," << p.second << ")";
  return os;
}
template <class T, class U, class V>
inline istream& operator>>(istream& is, tuple<T, U, V>& t) {
  is >> get<0>(t) >> get<1>(t) >> get<2>(t);
  return is;
}
template <class T, class U, class V>
inline ostream& operator<<(ostream& os, const tuple<T, U, V>& t) {
  os << "(" << get<0>(t) << "," << get<1>(t) << "," << get<2>(t) << ")";
  return os;
}
template <class T, class U, class V, class W>
inline istream& operator>>(istream& is, tuple<T, U, V, W>& t) {
  is >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t);
  return is;
}
template <class T, class U, class V, class W>
inline ostream& operator<<(ostream& os, const tuple<T, U, V, W>& t) {
  os << "(" << get<0>(t) << "," << get<1>(t) << "," << get<2>(t) << ","
     << get<3>(t) << ")";
  return os;
}
template <class T>
inline istream& operator>>(istream& is, vector<T>& v) {
  for (auto& x : (v)) is >> x;
  return is;
}
template <class T>
inline ostream& operator<<(ostream& os, const vector<T>& v) {
  for (const auto& x : (v)) os << x << " ";
  return os;
}
template <class T>
inline ostream& operator<<(ostream& os, const set<T>& s) {
  for (const auto& x : (s)) os << x << " ";
  return os;
}
template <class T>
inline ostream& operator<<(ostream& os, const unordered_set<T>& s) {
  for (const auto& x : (s)) os << x << " ";
  return os;
}
template <class T, class U>
inline ostream& operator<<(ostream& os, const map<T, U>& m) {
  for (const auto& p : (m)) os << p << " ";
  return os;
}
template <class T, class U>
inline ostream& operator<<(ostream& os, const unordered_map<T, U>& m) {
  for (const auto& p : (m)) os << p << " ";
  return os;
}
template <class T>
inline ostream& operator<<(ostream& os, stack<T> s) {
  while (!s.empty()) {
    os << s.top() << " ";
    s.pop();
  }
  return os;
}
template <class T>
inline ostream& operator<<(ostream& os, queue<T> q) {
  while (!q.empty()) {
    os << q.front() << " ";
    q.pop();
  }
  return os;
}
template <class T>
inline ostream& operator<<(ostream& os, deque<T> q) {
  while (!q.empty()) {
    os << q.front() << " ";
    q.pop_front();
  }
  return os;
}
template <class T>
inline ostream& operator<<(ostream& os, priority_queue<T> q) {
  while (!q.empty()) {
    os << q.top() << " ";
    q.pop();
  }
  return os;
}
int main() {
  int t;
  cin >> t;
  for (int hoge = 0, hoge_len = int(t); hoge < hoge_len; ++hoge) {
    int n;
    ll k;
    cin >> n >> k;
    vi a(n);
    cin >> a;
    a.push_back(18);
    ll res = 0;
    for (int i = int(1), i_end = int(n); i <= i_end; ++i) {
      ll m = pow(10, a[i] - a[i - 1]);
      if (k + 1 < m) {
        res += (k + 1) * pow(10, a[i - 1]);
        break;
      }
      res += (m - 1) * pow(10, a[i - 1]);
      k -= m - 1;
    }
    cout << res << "\n";
  }
}

### Prompt

Please provide a cpp coded solution to the problem described below:

In Berland, n different types of banknotes are used. Banknotes of the i-th type have denomination 10^{a_i} burles (burles are the currency used in Berland); the denomination of banknotes of the first type is exactly 1.

Let's denote f(s) as the minimum number of banknotes required to represent exactly s burles. For example, if the denominations of banknotes used in Berland are 1, 10 and 100, then f(59) = 14: 9 banknotes with denomination of 1 burle and 5 banknotes with denomination of 10 burles can be used to represent exactly 9 ⋅ 1 + 5 ⋅ 10 = 59 burles, and there's no way to do it with fewer banknotes.

For a given integer k, find the minimum positive number of burles s that cannot be represented with k or fewer banknotes (that is, f(s) > k).

Input

The first line contains a single integer t (1 ≤ t ≤ 10^4) — number of test cases.

The first line of each test case contains two integers n and k (1 ≤ n ≤ 10; 1 ≤ k ≤ 10^9).

The next line contains n integers a_1, a_2, ..., a_n (0 = a_1 < a_2 < ... < a_n ≤ 9).

Output

For each test case, print one integer — the minimum positive number of burles s that cannot be represented with k or fewer banknotes.

Example

Input


4
3 13
0 1 2
2 777
0 4
3 255
0 1 3
10 1000000000
0 1 2 3 4 5 6 7 8 9


Output


59
778
148999
999999920999999999

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vvvl = vector<vvl>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vvvb = vector<vvb>;
using vc = vector<char>;
using vvc = vector<vc>;
using vvvc = vector<vvc>;
using vd = vector<double>;
using vvd = vector<vd>;
using vvvd = vector<vvd>;
template <class T>
using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>;
using Graph = vvi;
const double PI = 3.14159265359;
const double DEG = PI / 180.;
const vi dx4 = {1, 0, -1, 0};
const vi dy4 = {0, 1, 0, -1};
const vi dx8 = {1, 1, 0, -1, -1, -1, 0, 1};
const vi dy8 = {0, 1, 1, 1, 0, -1, -1, -1};
const int INF = 1001001001;
const ll INFL = 2002002002002002002LL;
const double EPS = 1e-10;
struct fast_io {
  fast_io() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
  }
} fast_io_tmp;
template <class T>
inline ll pow(T n, int k) {
  ll v = 1;
  for (int i = 0, i_len = int(k); i < i_len; ++i) v *= n;
  return v;
}
template <class T>
inline bool chmax(T& M, const T& x) {
  if (M < x) {
    M = x;
    return true;
  }
  return false;
}
template <class T>
inline bool chmin(T& m, const T& x) {
  if (m > x) {
    m = x;
    return true;
  }
  return false;
}
template <class T, class U>
inline istream& operator>>(istream& is, pair<T, U>& p) {
  is >> p.first >> p.second;
  return is;
}
template <class T, class U>
inline ostream& operator<<(ostream& os, const pair<T, U>& p) {
  os << "(" << p.first << "," << p.second << ")";
  return os;
}
template <class T, class U, class V>
inline istream& operator>>(istream& is, tuple<T, U, V>& t) {
  is >> get<0>(t) >> get<1>(t) >> get<2>(t);
  return is;
}
template <class T, class U, class V>
inline ostream& operator<<(ostream& os, const tuple<T, U, V>& t) {
  os << "(" << get<0>(t) << "," << get<1>(t) << "," << get<2>(t) << ")";
  return os;
}
template <class T, class U, class V, class W>
inline istream& operator>>(istream& is, tuple<T, U, V, W>& t) {
  is >> get<0>(t) >> get<1>(t) >> get<2>(t) >> get<3>(t);
  return is;
}
template <class T, class U, class V, class W>
inline ostream& operator<<(ostream& os, const tuple<T, U, V, W>& t) {
  os << "(" << get<0>(t) << "," << get<1>(t) << "," << get<2>(t) << ","
     << get<3>(t) << ")";
  return os;
}
template <class T>
inline istream& operator>>(istream& is, vector<T>& v) {
  for (auto& x : (v)) is >> x;
  return is;
}
template <class T>
inline ostream& operator<<(ostream& os, const vector<T>& v) {
  for (const auto& x : (v)) os << x << " ";
  return os;
}
template <class T>
inline ostream& operator<<(ostream& os, const set<T>& s) {
  for (const auto& x : (s)) os << x << " ";
  return os;
}
template <class T>
inline ostream& operator<<(ostream& os, const unordered_set<T>& s) {
  for (const auto& x : (s)) os << x << " ";
  return os;
}
template <class T, class U>
inline ostream& operator<<(ostream& os, const map<T, U>& m) {
  for (const auto& p : (m)) os << p << " ";
  return os;
}
template <class T, class U>
inline ostream& operator<<(ostream& os, const unordered_map<T, U>& m) {
  for (const auto& p : (m)) os << p << " ";
  return os;
}
template <class T>
inline ostream& operator<<(ostream& os, stack<T> s) {
  while (!s.empty()) {
    os << s.top() << " ";
    s.pop();
  }
  return os;
}
template <class T>
inline ostream& operator<<(ostream& os, queue<T> q) {
  while (!q.empty()) {
    os << q.front() << " ";
    q.pop();
  }
  return os;
}
template <class T>
inline ostream& operator<<(ostream& os, deque<T> q) {
  while (!q.empty()) {
    os << q.front() << " ";
    q.pop_front();
  }
  return os;
}
template <class T>
inline ostream& operator<<(ostream& os, priority_queue<T> q) {
  while (!q.empty()) {
    os << q.top() << " ";
    q.pop();
  }
  return os;
}
int main() {
  int t;
  cin >> t;
  for (int hoge = 0, hoge_len = int(t); hoge < hoge_len; ++hoge) {
    int n;
    ll k;
    cin >> n >> k;
    vi a(n);
    cin >> a;
    a.push_back(18);
    ll res = 0;
    for (int i = int(1), i_end = int(n); i <= i_end; ++i) {
      ll m = pow(10, a[i] - a[i - 1]);
      if (k + 1 < m) {
        res += (k + 1) * pow(10, a[i - 1]);
        break;
      }
      res += (m - 1) * pow(10, a[i - 1]);
      k -= m - 1;
    }
    cout << res << "\n";
  }
}

```