#include <bits/stdc++.h>
using namespace std;
struct IOReader {
  template <typename T>
  inline IOReader& operator>>(T& a) {
    a = 0;
    bool flg = false;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
      if (ch == '-') flg ^= 1;
      ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
      a = (a << 3) + (a << 1) + (ch ^ '0');
      ch = getchar();
    }
    if (flg) a = -a;
    return *this;
  }
  inline IOReader& operator>>(string& a) {
    a.clear();
    char ch = getchar();
    while (isspace(ch) && ch != EOF) ch = getchar();
    while (!isspace(ch) && ch != EOF) a += ch, ch = getchar();
    return *this;
  }
  inline IOReader& operator>>(char* a) {
    scanf(" %s", a);
    return *this;
  }
  inline IOReader& operator>>(char& a) {
    a = getchar();
    while (isspace(a)) a = getchar();
    return *this;
  }
  inline IOReader& operator>>(float& a) {
    a = 0;
    bool flg = false;
    char ch = getchar();
    while ((ch < '0' || ch > '9') && ch != '.') {
      if (ch == '-') flg ^= 1;
      ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
      a = a * 10 + (ch ^ '0');
      ch = getchar();
    }
    if (ch == '.') {
      ch = getchar();
      float p = 0.1;
      while (ch >= '0' && ch <= '9') {
        a += p * (ch ^ '0');
        ch = getchar();
        p *= 0.1;
      }
    }
    if (flg) a = -a;
    return *this;
  }
  inline IOReader& operator>>(double& a) {
    a = 0;
    bool flg = false;
    char ch = getchar();
    while ((ch < '0' || ch > '9') && ch != '.') {
      if (ch == '-') flg ^= 1;
      ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
      a = a * 10 + (ch ^ '0');
      ch = getchar();
    }
    if (ch == '.') {
      ch = getchar();
      double p = 0.1;
      while (ch >= '0' && ch <= '9') {
        a += p * (ch ^ '0');
        ch = getchar();
        p *= 0.1;
      }
    }
    if (flg) a = -a;
    return *this;
  }
  inline IOReader& operator>>(long double& a) {
    a = 0;
    bool flg = false;
    char ch = getchar();
    while ((ch < '0' || ch > '9') && ch != '.') {
      if (ch == '-') flg ^= 1;
      ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
      a = a * 10 + (ch ^ '0');
      ch = getchar();
    }
    if (ch == '.') {
      ch = getchar();
      long double p = 0.1;
      while (ch >= '0' && ch <= '9') {
        a += p * (ch ^ '0');
        ch = getchar();
        p *= 0.1;
      }
    }
    if (flg) a = -a;
    return *this;
  }
} iocin;
int readInt() {
  int a = 0;
  bool flg = false;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') flg ^= 1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    a = (a << 3) + (a << 1) + (ch ^ '0');
    ch = getchar();
  }
  if (flg) a = -a;
  return a;
}
unsigned int readUInt() {
  unsigned int a = 0;
  bool flg = false;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') flg ^= 1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    a = (a << 3) + (a << 1) + (ch ^ '0');
    ch = getchar();
  }
  if (flg) a = -a;
  return a;
}
long long readLL() {
  long long a = 0;
  bool flg = false;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') flg ^= 1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    a = (a << 3) + (a << 1) + (ch ^ '0');
    ch = getchar();
  }
  if (flg) a = -a;
  return a;
}
unsigned long long readULL() {
  unsigned long long a = 0;
  bool flg = false;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') flg ^= 1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    a = (a << 3) + (a << 1) + (ch ^ '0');
    ch = getchar();
  }
  if (flg) a = -a;
  return a;
}
short readShort() {
  short a = 0;
  bool flg = false;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') flg ^= 1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    a = (a << 3) + (a << 1) + (ch ^ '0');
    ch = getchar();
  }
  if (flg) a = -a;
  return a;
}
unsigned short readUShort() {
  unsigned short a = 0;
  bool flg = false;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') flg ^= 1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    a = (a << 3) + (a << 1) + (ch ^ '0');
    ch = getchar();
  }
  if (flg) a = -a;
  return a;
}
float readFL() {
  float a = 0;
  bool flg = false;
  char ch = getchar();
  while ((ch < '0' || ch > '9') && ch != '.') {
    if (ch == '-') flg ^= 1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    a = a * 10 + (ch ^ '0');
    ch = getchar();
  }
  if (ch == '.') {
    ch = getchar();
    float p = 0.1;
    while (ch >= '0' && ch <= '9') {
      a += p * (ch ^ '0');
      ch = getchar();
      p *= 0.1;
    }
  }
  if (flg) a = -a;
  return a;
}
double readDB() {
  double a = 0;
  bool flg = false;
  char ch = getchar();
  while ((ch < '0' || ch > '9') && ch != '.') {
    if (ch == '-') flg ^= 1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    a = a * 10 + (ch ^ '0');
    ch = getchar();
  }
  if (ch == '.') {
    ch = getchar();
    double p = 0.1;
    while (ch >= '0' && ch <= '9') {
      a += p * (ch ^ '0');
      ch = getchar();
      p *= 0.1;
    }
  }
  if (flg) a = -a;
  return a;
}
long double readLDB() {
  long double a = 0;
  bool flg = false;
  char ch = getchar();
  while ((ch < '0' || ch > '9') && ch != '.') {
    if (ch == '-') flg ^= 1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    a = a * 10 + (ch ^ '0');
    ch = getchar();
  }
  if (ch == '.') {
    ch = getchar();
    long double p = 0.1;
    while (ch >= '0' && ch <= '9') {
      a += p * (ch ^ '0');
      ch = getchar();
      p *= 0.1;
    }
  }
  if (flg) a = -a;
  return a;
}
inline void yOn(bool x) { printf("%s", (x) ? "Yes" : "No"); }
inline void yOn(bool x, char* str) { printf("%s%s", (x) ? "Yes" : "No", str); }
inline void yOn(bool x, char str) { printf("%s%c", (x) ? "Yes" : "No", str); }
inline void yOn(bool x, const char* str) {
  printf("%s%s", (x) ? "Yes" : "No", str);
}
inline void yOn(bool x, string str) {
  printf("%s%s", (x) ? "Yes" : "No", str.c_str());
}
inline void YON(bool x) { printf("%s", (x) ? "YES" : "NO"); }
inline void YON(bool x, char* str) { printf("%s%s", (x) ? "YES" : "NO", str); }
inline void YON(bool x, char str) { printf("%s%c", (x) ? "YES" : "NO", str); }
inline void YON(bool x, const char* str) {
  printf("%s%s", (x) ? "YES" : "NO", str);
}
inline void YON(bool x, string str) {
  printf("%s%s", (x) ? "YES" : "NO", str.c_str());
}
int N, A[15];
long long K;
inline long long Pow10(int x) {
  long long ret = 1;
  while (x--) ret *= 10;
  return ret;
}
int main() {
  int totCases;
  iocin >> totCases;
  for (int currCase = 1; currCase <= totCases; currCase++) {
    iocin >> N >> K;
    ++K;
    for (int tiger2005 = 1; tiger2005 <= N; tiger2005++) iocin >> A[tiger2005];
    string ans = "";
    bool flg = false;
    for (int i = 2; i <= N; i++) {
      long long p = Pow10(A[i] - A[i - 1]) - 1;
      if (K >= p)
        for (int j = A[i - 1]; j < A[i]; j++) ans += '9';
      else {
        if (K != 0) ans = to_string(K) + ans;
        flg = true;
        break;
      }
      K -= p;
    }
    if (!flg && K != 0) ans = to_string(K) + ans;
    printf("%s\n", ans.c_str());
  }
  return 0;
}

### Prompt

Create a solution in CPP for the following problem:

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;
struct IOReader {
  template <typename T>
  inline IOReader& operator>>(T& a) {
    a = 0;
    bool flg = false;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
      if (ch == '-') flg ^= 1;
      ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
      a = (a << 3) + (a << 1) + (ch ^ '0');
      ch = getchar();
    }
    if (flg) a = -a;
    return *this;
  }
  inline IOReader& operator>>(string& a) {
    a.clear();
    char ch = getchar();
    while (isspace(ch) && ch != EOF) ch = getchar();
    while (!isspace(ch) && ch != EOF) a += ch, ch = getchar();
    return *this;
  }
  inline IOReader& operator>>(char* a) {
    scanf(" %s", a);
    return *this;
  }
  inline IOReader& operator>>(char& a) {
    a = getchar();
    while (isspace(a)) a = getchar();
    return *this;
  }
  inline IOReader& operator>>(float& a) {
    a = 0;
    bool flg = false;
    char ch = getchar();
    while ((ch < '0' || ch > '9') && ch != '.') {
      if (ch == '-') flg ^= 1;
      ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
      a = a * 10 + (ch ^ '0');
      ch = getchar();
    }
    if (ch == '.') {
      ch = getchar();
      float p = 0.1;
      while (ch >= '0' && ch <= '9') {
        a += p * (ch ^ '0');
        ch = getchar();
        p *= 0.1;
      }
    }
    if (flg) a = -a;
    return *this;
  }
  inline IOReader& operator>>(double& a) {
    a = 0;
    bool flg = false;
    char ch = getchar();
    while ((ch < '0' || ch > '9') && ch != '.') {
      if (ch == '-') flg ^= 1;
      ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
      a = a * 10 + (ch ^ '0');
      ch = getchar();
    }
    if (ch == '.') {
      ch = getchar();
      double p = 0.1;
      while (ch >= '0' && ch <= '9') {
        a += p * (ch ^ '0');
        ch = getchar();
        p *= 0.1;
      }
    }
    if (flg) a = -a;
    return *this;
  }
  inline IOReader& operator>>(long double& a) {
    a = 0;
    bool flg = false;
    char ch = getchar();
    while ((ch < '0' || ch > '9') && ch != '.') {
      if (ch == '-') flg ^= 1;
      ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
      a = a * 10 + (ch ^ '0');
      ch = getchar();
    }
    if (ch == '.') {
      ch = getchar();
      long double p = 0.1;
      while (ch >= '0' && ch <= '9') {
        a += p * (ch ^ '0');
        ch = getchar();
        p *= 0.1;
      }
    }
    if (flg) a = -a;
    return *this;
  }
} iocin;
int readInt() {
  int a = 0;
  bool flg = false;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') flg ^= 1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    a = (a << 3) + (a << 1) + (ch ^ '0');
    ch = getchar();
  }
  if (flg) a = -a;
  return a;
}
unsigned int readUInt() {
  unsigned int a = 0;
  bool flg = false;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') flg ^= 1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    a = (a << 3) + (a << 1) + (ch ^ '0');
    ch = getchar();
  }
  if (flg) a = -a;
  return a;
}
long long readLL() {
  long long a = 0;
  bool flg = false;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') flg ^= 1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    a = (a << 3) + (a << 1) + (ch ^ '0');
    ch = getchar();
  }
  if (flg) a = -a;
  return a;
}
unsigned long long readULL() {
  unsigned long long a = 0;
  bool flg = false;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') flg ^= 1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    a = (a << 3) + (a << 1) + (ch ^ '0');
    ch = getchar();
  }
  if (flg) a = -a;
  return a;
}
short readShort() {
  short a = 0;
  bool flg = false;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') flg ^= 1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    a = (a << 3) + (a << 1) + (ch ^ '0');
    ch = getchar();
  }
  if (flg) a = -a;
  return a;
}
unsigned short readUShort() {
  unsigned short a = 0;
  bool flg = false;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') flg ^= 1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    a = (a << 3) + (a << 1) + (ch ^ '0');
    ch = getchar();
  }
  if (flg) a = -a;
  return a;
}
float readFL() {
  float a = 0;
  bool flg = false;
  char ch = getchar();
  while ((ch < '0' || ch > '9') && ch != '.') {
    if (ch == '-') flg ^= 1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    a = a * 10 + (ch ^ '0');
    ch = getchar();
  }
  if (ch == '.') {
    ch = getchar();
    float p = 0.1;
    while (ch >= '0' && ch <= '9') {
      a += p * (ch ^ '0');
      ch = getchar();
      p *= 0.1;
    }
  }
  if (flg) a = -a;
  return a;
}
double readDB() {
  double a = 0;
  bool flg = false;
  char ch = getchar();
  while ((ch < '0' || ch > '9') && ch != '.') {
    if (ch == '-') flg ^= 1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    a = a * 10 + (ch ^ '0');
    ch = getchar();
  }
  if (ch == '.') {
    ch = getchar();
    double p = 0.1;
    while (ch >= '0' && ch <= '9') {
      a += p * (ch ^ '0');
      ch = getchar();
      p *= 0.1;
    }
  }
  if (flg) a = -a;
  return a;
}
long double readLDB() {
  long double a = 0;
  bool flg = false;
  char ch = getchar();
  while ((ch < '0' || ch > '9') && ch != '.') {
    if (ch == '-') flg ^= 1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    a = a * 10 + (ch ^ '0');
    ch = getchar();
  }
  if (ch == '.') {
    ch = getchar();
    long double p = 0.1;
    while (ch >= '0' && ch <= '9') {
      a += p * (ch ^ '0');
      ch = getchar();
      p *= 0.1;
    }
  }
  if (flg) a = -a;
  return a;
}
inline void yOn(bool x) { printf("%s", (x) ? "Yes" : "No"); }
inline void yOn(bool x, char* str) { printf("%s%s", (x) ? "Yes" : "No", str); }
inline void yOn(bool x, char str) { printf("%s%c", (x) ? "Yes" : "No", str); }
inline void yOn(bool x, const char* str) {
  printf("%s%s", (x) ? "Yes" : "No", str);
}
inline void yOn(bool x, string str) {
  printf("%s%s", (x) ? "Yes" : "No", str.c_str());
}
inline void YON(bool x) { printf("%s", (x) ? "YES" : "NO"); }
inline void YON(bool x, char* str) { printf("%s%s", (x) ? "YES" : "NO", str); }
inline void YON(bool x, char str) { printf("%s%c", (x) ? "YES" : "NO", str); }
inline void YON(bool x, const char* str) {
  printf("%s%s", (x) ? "YES" : "NO", str);
}
inline void YON(bool x, string str) {
  printf("%s%s", (x) ? "YES" : "NO", str.c_str());
}
int N, A[15];
long long K;
inline long long Pow10(int x) {
  long long ret = 1;
  while (x--) ret *= 10;
  return ret;
}
int main() {
  int totCases;
  iocin >> totCases;
  for (int currCase = 1; currCase <= totCases; currCase++) {
    iocin >> N >> K;
    ++K;
    for (int tiger2005 = 1; tiger2005 <= N; tiger2005++) iocin >> A[tiger2005];
    string ans = "";
    bool flg = false;
    for (int i = 2; i <= N; i++) {
      long long p = Pow10(A[i] - A[i - 1]) - 1;
      if (K >= p)
        for (int j = A[i - 1]; j < A[i]; j++) ans += '9';
      else {
        if (K != 0) ans = to_string(K) + ans;
        flg = true;
        break;
      }
      K -= p;
    }
    if (!flg && K != 0) ans = to_string(K) + ans;
    printf("%s\n", ans.c_str());
  }
  return 0;
}

```