#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 7;
const int maxm = 26e3 + 7;
const long long mod = 998244353;
int n, k;
int flag[12];
vector<int> v;
string s;
int check(int pos) {
  set<int> second;
  for (int i = (0); i <= (pos); ++i) {
    second.insert(s[i] - '0');
  }
  return (second.size() < k);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    cin >> s >> k;
    memset(flag, 0, sizeof(flag));
    v.clear();
    int pos = -1;
    for (int i = (0), __ = (s.size()); i < __; ++i) {
      if (!flag[s[i] - '0']) {
        if (v.size() == k) {
          pos = i;
          break;
        } else
          flag[s[i] - '0']++, v.push_back(s[i] - '0');
      }
    }
    if (pos == -1) {
      cout << s << '\n';
      continue;
    }
    sort(v.begin(), v.end());
    int tb = 0;
    for (int i = pos; i >= 0; i--) {
      int p = upper_bound(v.begin(), v.end(), s[i] - '0') - v.begin();
      if (check(i - 1) && s[i] != '9') {
        int fd = 0;
        for (int j = 0; j < v.size(); j++) {
          if (s[i] - '0' == v[j])
            v.erase(v.begin() + j), j--;
          else if (s[i] - '0' + 1 == v[j])
            fd = 1;
        }
        if (!fd) {
          v.push_back(s[i] - '0' + 1);
          sort(v.begin(), v.end());
        }
        s[i] = char(s[i] + 1);
        pos = i;
        break;
      } else if (p != v.size()) {
        s[i] = char(v[p] + '0');
        pos = i;
        break;
      }
      if (!i) tb = 1;
    }
    if (v.size() < k) v[0] = 0;
    if (tb) {
      if (k == 1) {
        for (int i = (1); i <= (s.size() + 1); ++i) cout << 1;
      } else {
        cout << 1;
        for (int i = (1); i <= (s.size()); ++i) cout << 0;
      }
    } else {
      for (int i = (0); i <= (pos); ++i) cout << s[i];
      for (int i = (pos + 1), __ = (s.size()); i < __; ++i) cout << v[0];
    }
    cout << '\n';
  }
}

### Prompt

Please formulate a cpp solution to the following problem:

It is a complicated version of problem F1. The difference between them is the constraints (F1: k ≤ 2, F2: k ≤ 10).

You are given an integer n. Find the minimum integer x such that x ≥ n and the number x is k-beautiful.

A number is called k-beautiful if its decimal representation having no leading zeroes contains no more than k different digits. E.g. if k = 2, the numbers 3434443, 55550, 777 and 21 are k-beautiful whereas the numbers 120, 445435 and 998244353 are not.

Input

The first line contains one integer t (1 ≤ t ≤ 10^4) — the number of test cases. Then t test cases follow.

Each test case consists of one line containing two integers n and k (1 ≤ n ≤ 10^9, 1 ≤ k ≤ 10).

Output

For each test case output on a separate line x — the minimum k-beautiful integer such that x ≥ n.

Example

Input


6
2021 3
177890 2
34512 3
724533 4
998244353 1
12345678 10


Output


2021
181111
34533
724542
999999999
12345678

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 7;
const int maxm = 26e3 + 7;
const long long mod = 998244353;
int n, k;
int flag[12];
vector<int> v;
string s;
int check(int pos) {
  set<int> second;
  for (int i = (0); i <= (pos); ++i) {
    second.insert(s[i] - '0');
  }
  return (second.size() < k);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    cin >> s >> k;
    memset(flag, 0, sizeof(flag));
    v.clear();
    int pos = -1;
    for (int i = (0), __ = (s.size()); i < __; ++i) {
      if (!flag[s[i] - '0']) {
        if (v.size() == k) {
          pos = i;
          break;
        } else
          flag[s[i] - '0']++, v.push_back(s[i] - '0');
      }
    }
    if (pos == -1) {
      cout << s << '\n';
      continue;
    }
    sort(v.begin(), v.end());
    int tb = 0;
    for (int i = pos; i >= 0; i--) {
      int p = upper_bound(v.begin(), v.end(), s[i] - '0') - v.begin();
      if (check(i - 1) && s[i] != '9') {
        int fd = 0;
        for (int j = 0; j < v.size(); j++) {
          if (s[i] - '0' == v[j])
            v.erase(v.begin() + j), j--;
          else if (s[i] - '0' + 1 == v[j])
            fd = 1;
        }
        if (!fd) {
          v.push_back(s[i] - '0' + 1);
          sort(v.begin(), v.end());
        }
        s[i] = char(s[i] + 1);
        pos = i;
        break;
      } else if (p != v.size()) {
        s[i] = char(v[p] + '0');
        pos = i;
        break;
      }
      if (!i) tb = 1;
    }
    if (v.size() < k) v[0] = 0;
    if (tb) {
      if (k == 1) {
        for (int i = (1); i <= (s.size() + 1); ++i) cout << 1;
      } else {
        cout << 1;
        for (int i = (1); i <= (s.size()); ++i) cout << 0;
      }
    } else {
      for (int i = (0); i <= (pos); ++i) cout << s[i];
      for (int i = (pos + 1), __ = (s.size()); i < __; ++i) cout << v[0];
    }
    cout << '\n';
  }
}

```