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>
  #pragma GCC optimize(3)
  #pragma GCC optimize("Ofast")
  using namespace std;
  const double pi = acos(-1.0);
  const int inf = 0x3f3f3f3f;
  const long long INF = 0x3f3f3f3f3f3f3f3fll;
  int dir[4][2] = {{1, 0}, {0, -1}, {-1, 0}, {0, 1}};
  long long read() {
    long long x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
      if (c == '-') f = -1;
      c = getchar();
    }
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
  }
  void wri(long long x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) wri(x / 10);
    putchar(x % 10 + '0');
  }
  void write(long long x) {
    wri(x);
    puts("");
  }
  long long ksc(long long a, long long b, long long mod) {
    return ((a * b -
             (long long)((long long)((long double)a / mod * b + 1e-3) * mod)) %
                mod +
            mod) %
           mod;
  }
  long long ksm1(long long a, long long n, long long mod) {
    long long t = 1;
    for (; n; n >>= 1, (a *= a) %= mod)
      if (n & 1) (t *= a) %= mod;
    return t;
  }
  long long ksm2(long long a, long long b, long long mod) {
    long long res = 1;
    while (b) {
      if (b & 1) res = ksc(res, a, mod);
      b >>= 1, a = ksc(a, a, mod);
    }
    return res % mod;
  }
  int is2pow(long long x) { return x > 0 ? (x & (x - 1)) == 0 : 0; }
  long long myrand(long long l, long long r) {
    long long num = ((long long)rand() << 30) | ((long long)rand());
    return num % (r + 1 - l) + l;
  }
  const long long N = 15;
  long long cnt[N];
  long long last[N];
  string solve(long long n) {
    string str = "";
    while (n) {
      str += n % 10 + '0';
      n /= 10;
    }
    reverse(str.begin(), str.end());
    return str;
  }
  signed main() {
    long long t;
    cin >> t;
    while (t--) {
      long long n, k;
      cin >> n >> k;
      memset(cnt, 0, sizeof(cnt));
      memset(last, 0, sizeof(last));
      long long geshu = 0;
      string tmp = solve(n);
      string res = "";
      long long mark = 0;
      char minn = '9';
      char maxnn = '0';
      for (long long i = 0; i < tmp.size(); i++) {
        if (geshu < k) {
          if (cnt[tmp[i] - '0'] == 0) {
            cnt[tmp[i] - '0'] = i + 1;
            last[tmp[i] - '0'] = i + 1;
            geshu++;
            res += tmp[i];
            minn = ((minn < tmp[i]) ? minn : tmp[i]);
            maxnn = ((maxnn > tmp[i]) ? maxnn : tmp[i]);
          } else
            res += tmp[i], minn = ((minn < tmp[i]) ? minn : tmp[i]),
                           last[tmp[i] - '0'] = i + 1;
        } else if (geshu == k) {
          if (mark == 0 && cnt[tmp[i] - '0'] == 0) {
            for (long long j = 0; j <= 9; j++) {
              if (cnt[j] && j >= tmp[i] - '0') {
                res += j + '0';
                mark = 1;
                break;
              }
            }
            if (mark == 0) {
              for (long long j = 0; j <= 9; j++) {
                if (cnt[j] && j > res.back() - '0') {
                  res.back() = j + '0';
                  res += minn;
                  mark = 1;
                  break;
                }
              }
            }
            if (mark == 0) {
              mark = 1;
              long long maxn = 0;
              char ch = '0';
              for (long long j = 0; j <= 9; j++) {
                if (cnt[j] > maxn) {
                  maxn = cnt[j];
                  ch = j + '0';
                }
              }
              long long woc = 0;
              long long wori = 0;
              for (long long i = 0; i < maxnn - '0'; i++)
                wori = ((wori > last[i]) ? wori : last[i]);
              if (wori > maxn) {
                for (long long j = 0; j <= 9; j++)
                  if (cnt[j] && j > tmp[wori - 1] - '0') {
                    res[wori - 1] = j + '0';
                    mark = 1;
                    for (long long j = wori; j < i; j++) res[j] = minn;
                    res += minn;
                    woc = 1;
                    break;
                  }
                if (woc) continue;
              }
              maxn--;
              if (minn == ch) minn++;
              res[maxn] = ch + 1;
              for (long long j = maxn + 1; j < i; j++) res[j] = minn;
              res += minn;
            }
          } else if (mark == 1)
            res += minn;
          else
            res += tmp[i], last[tmp[i] - '0'] = i + 1;
        }
      }
      long long pos = -1;
      for (long long i = 0; i < tmp.size(); i++) {
        if (res[i] > tmp[i]) {
          pos = i;
          break;
        }
      }
      if (pos != -1) {
        long long geshu2 = 0;
        vector<long long> vv;
        vv.clear();
        vv.resize(11);
        for (long long i = 0; i <= pos; i++) vv[res[i] - '0']++;
        for (long long i = 0; i <= 9; i++)
          if (vv[i]) geshu2++;
        if (geshu2 < k) {
          if (res[pos] != tmp[pos] + 1) {
            res[pos] = tmp[pos] + 1;
            char minn = '9';
            for (long long i = 0; i <= pos; i++)
              minn = ((minn < res[i]) ? minn : res[i]);
            for (long long i = pos + 1; i < res.size(); i++) res[i] = minn;
          } else {
            for (long long i = pos + 1; i < res.size(); i++) res[i] = '0';
          }
        }
      }
      cout << res << endl;
    }
    return 0;
  }
  