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;
  int dadsadasda;
  const int INF = 0x3f3f3f3f;
  const long long LLINF = 1e16;
  const int MAXN = 1e5;
  string N;
  int K;
  int count_bits(int k) {
    int cnt = 0;
    while (k > 0) {
      cnt += k & 1;
      k >>= 1;
    }
    return cnt;
  }
  long long tenP[12];
  long long go(vector<bool> digits) {
    bool cover_all = true;
    for (auto d : N) cover_all &= digits[d - '0'];
    if (cover_all) return stol(N);
    int smallest = 69;
    for (int i = 0; i < 10; i++)
      if (digits[i]) smallest = min(smallest, i);
    vector<int> nxt(12, 69);
    for (int i = 0; i < 10; i++)
      if (digits[i]) nxt[i] = i;
    for (int i = 8; i >= 0; --i) nxt[i] = min(nxt[i], nxt[i + 1]);
    vector<int> R((int)N.size() + 2);
    R[(int)N.size() - 1] = smallest;
    for (int i = (int)N.size() - 2; i >= 0; --i) R[i] = 10 * R[i + 1] + smallest;
    long long ans = LLINF;
    long long l = 0;
    for (int mid = 0; mid < (int)N.size(); ++mid) {
      if (nxt[N[mid] - '0' + 1] != 69)
        ans = min(ans, l + nxt[N[mid] - '0' + 1] * tenP[(int)N.size() - 1 - mid] +
                           R[mid + 1]);
      if (nxt[N[mid] - '0'] != 69)
        l = l + nxt[N[mid] - '0'] * tenP[(int)N.size() - 1 - mid];
      else
        break;
    }
    return ans;
  }
  map<pair<string, int>, long long> DP;
  void solve() {
    cin >> N >> K;
    if (DP.find({N, K}) != DP.end()) {
      printf("%lld\n", DP[{N, K}]);
      return;
    }
    long long ans = LLINF;
    for (int i = 1; i < (1 << 10); i++)
      if (count_bits(i) == K) {
        vector<bool> can_use(10);
        for (int b = 0; b < 10; b++)
          if ((i >> b) & 1) can_use[b] = 1;
        ans = min(ans, go(can_use));
      }
    DP[{N, K}] = ans;
    printf("%lld\n", ans);
  }
  int main() {
    tenP[0] = 1;
    for (int i = 1; i < 12; i++) tenP[i] = 10 * tenP[i - 1];
    int t;
    dadsadasda = scanf("%d", &t);
    while (t--) solve();
    return 0;
  }
  