description: 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
solution: #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;
      }
    }
  }
  