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;
  const int inf = 0x3f3f3f3f;
  const int N = 26;
  template <typename T>
  inline bool scan_d(T& ret) {
    char c;
    int sgn;
    if (c = getchar(), c == EOF) return 0;
    while (c != '-' && (c < '0' || c > '9')) {
      if ((c = getchar()) == EOF) return 0;
    }
    sgn = (c == '-') ? -1 : 1;
    ret = (c == '-') ? 0 : (c - '0');
    while (c = getchar(), c >= '0' && c <= '9') ret = ret * 10 + (c - '0');
    ret *= sgn;
    return 1;
  }
  template <typename T>
  void print(T x) {
    static char s[33], *s1;
    s1 = s;
    if (!x) *s1++ = '0';
    if (x < 0) putchar('-'), x = -x;
    while (x) *s1++ = (x % 10 + '0'), x /= 10;
    while (s1-- != s) putchar(*s1);
  }
  template <typename T>
  void println(T x) {
    print(x);
    putchar('\n');
  }
  int n, k;
  set<int> num2set(int val) {
    set<int> mset;
    while (val) {
      mset.insert(val % 10);
      val /= 10;
    }
    return mset;
  }
  int solve(int val) {
    while (true) {
      set<int> mset = num2set(val);
      if (mset.size() <= k) return val;
      if (val % 10 == 0) {
        int pre = val / 10;
        int spre = solve(pre);
        mset = num2set(spre);
        return spre * 10 + *mset.begin();
      }
      val++;
    }
    return 0;
  }
  int main() {
    int T;
    scan_d(T);
    for (int t = (0); t < (T); ++t) {
      scan_d(n), scan_d(k);
      println(solve(n));
    }
    return 0;
  }
  