#include <bits/stdc++.h>
using namespace std;
pair<vector<char>, bool> solve(set<char> useddigits, int k, string n) {
  if (n.length() == 0) {
    return {{}, true};
  }
  if (useddigits.find(n[0]) != useddigits.end()) {
    pair<vector<char>, bool> remainder =
        solve(useddigits, k, n.substr(1, n.size() - 1));
    if (remainder.second) {
      remainder.first.insert(remainder.first.begin(), n[0]);
      return remainder;
    }
  }
  if (k == 0) {
    for (char d : useddigits) {
      if (d == n[0]) {
        pair<vector<char>, bool> remainder =
            solve(useddigits, k, n.substr(1, n.size() - 1));
        if (remainder.second) {
          remainder.first.insert(remainder.first.begin(), d);
          return remainder;
        }
      } else if (d > n[0]) {
        char small = *min_element(useddigits.begin(), useddigits.end());
        vector<char> ans(n.size(), small);
        ans[0] = d;
        return {ans, true};
      }
    }
  } else if (k == 1) {
    set<char> copy = useddigits;
    copy.insert(n[0]);
    pair<vector<char>, bool> remainder = solve(copy, k - 1, n);
    if (remainder.second && remainder.first[0] == n[0]) return remainder;
    char small;
    if (useddigits.find(n[0] + 1) == useddigits.end()) {
      useddigits.insert(n[0] + 1);
      small = *min_element(useddigits.begin(), useddigits.end());
    } else
      small = '0';
    vector<char> ans(n.size(), small);
    ans[0] = n[0] + 1;
    return {ans, true};
  }
  return {{}, false};
}
int main() {
  int T;
  cin >> T;
  while (T--) {
    string n;
    int k;
    cin >> n >> k;
    vector<char> digits;
    set<char> useddigits;
    int i = 0;
    while (useddigits.size() < k - 1 && i < n.size()) {
      digits.push_back(n[i]);
      useddigits.insert(n[i]);
      i++;
    }
    if (i >= n.size()) {
      for (char j : digits) {
        cout << j;
      }
      cout << endl;
    } else {
      vector<char> remainder =
          solve(useddigits, 1, n.substr(i, n.size() - i)).first;
      for (char j : digits) {
        cout << j;
      }
      for (char j : remainder) {
        cout << j;
      }
      cout << endl;
    }
  }
}

### Prompt

Generate 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;
pair<vector<char>, bool> solve(set<char> useddigits, int k, string n) {
  if (n.length() == 0) {
    return {{}, true};
  }
  if (useddigits.find(n[0]) != useddigits.end()) {
    pair<vector<char>, bool> remainder =
        solve(useddigits, k, n.substr(1, n.size() - 1));
    if (remainder.second) {
      remainder.first.insert(remainder.first.begin(), n[0]);
      return remainder;
    }
  }
  if (k == 0) {
    for (char d : useddigits) {
      if (d == n[0]) {
        pair<vector<char>, bool> remainder =
            solve(useddigits, k, n.substr(1, n.size() - 1));
        if (remainder.second) {
          remainder.first.insert(remainder.first.begin(), d);
          return remainder;
        }
      } else if (d > n[0]) {
        char small = *min_element(useddigits.begin(), useddigits.end());
        vector<char> ans(n.size(), small);
        ans[0] = d;
        return {ans, true};
      }
    }
  } else if (k == 1) {
    set<char> copy = useddigits;
    copy.insert(n[0]);
    pair<vector<char>, bool> remainder = solve(copy, k - 1, n);
    if (remainder.second && remainder.first[0] == n[0]) return remainder;
    char small;
    if (useddigits.find(n[0] + 1) == useddigits.end()) {
      useddigits.insert(n[0] + 1);
      small = *min_element(useddigits.begin(), useddigits.end());
    } else
      small = '0';
    vector<char> ans(n.size(), small);
    ans[0] = n[0] + 1;
    return {ans, true};
  }
  return {{}, false};
}
int main() {
  int T;
  cin >> T;
  while (T--) {
    string n;
    int k;
    cin >> n >> k;
    vector<char> digits;
    set<char> useddigits;
    int i = 0;
    while (useddigits.size() < k - 1 && i < n.size()) {
      digits.push_back(n[i]);
      useddigits.insert(n[i]);
      i++;
    }
    if (i >= n.size()) {
      for (char j : digits) {
        cout << j;
      }
      cout << endl;
    } else {
      vector<char> remainder =
          solve(useddigits, 1, n.substr(i, n.size() - i)).first;
      for (char j : digits) {
        cout << j;
      }
      for (char j : remainder) {
        cout << j;
      }
      cout << endl;
    }
  }
}

```