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;
  using ll = long long;
  constexpr int INF = 0x3f3f3f3f;
  constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
  constexpr double EPS = 1e-8;
  constexpr int MOD = 1000000007;
  constexpr int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1};
  constexpr int dy8[] = {1, 1, 0, -1, -1, -1, 0, 1},
                dx8[] = {0, -1, -1, -1, 0, 1, 1, 1};
  template <typename T, typename U>
  inline bool chmax(T &a, U b) {
    return a < b ? (a = b, true) : false;
  }
  template <typename T, typename U>
  inline bool chmin(T &a, U b) {
    return a > b ? (a = b, true) : false;
  }
  struct IOSetup {
    IOSetup() {
      std::cin.tie(nullptr);
      std::ios_base::sync_with_stdio(false);
      std::cout << fixed << setprecision(20);
    }
  } iosetup;
  constexpr int D = 10;
  void solve() {
    string n;
    int k;
    cin >> n >> k;
    ll N = stoll(n);
    const int l = n.length();
    vector<ll> w(l, 1);
    for (int i = l - 2; i >= 0; --i) w[i] = w[i + 1] * 10;
    vector<ll> sum = w;
    for (int i = l - 2; i >= 0; --i) sum[i] += sum[i + 1];
    int lb = 0, ub = l + 1;
    while (ub - lb > 1) {
      int mid = (lb + ub) / 2;
      set<int> digit;
      ll num = 0;
      for (int i = (0); i < (mid); ++i) {
        num += w[i] * (n[i] - '0');
        digit.emplace(n[i] - '0');
      }
      if (digit.size() > k) {
        ub = mid;
        continue;
      } else if (digit.size() == k) {
        if (mid < l) num += sum[mid] * *digit.rbegin();
      } else {
        if (mid < l) num += sum[mid] * 9;
      }
      (num >= N ? lb : ub) = mid;
    }
    if (lb == l) {
      cout << N << '\n';
      return;
    }
    ll ans = 0;
    set<int> digit;
    for (int i = (0); i < (lb); ++i) {
      ans += w[i] * (n[i] - '0');
      digit.emplace(n[i] - '0');
    }
    for (int lb_d = (n[lb] - '0' + 1); lb_d < (D); ++lb_d) {
      set<int> tmp_digit = digit;
      tmp_digit.emplace(lb_d);
      if (tmp_digit.size() > k) continue;
      ll tmp_ans = ans + w[lb] * lb_d;
      if (lb + 1 < l)
        tmp_ans +=
            sum[lb + 1] * (tmp_digit.size() == k ? *tmp_digit.rbegin() : 9);
      if (tmp_ans >= N) {
        ans += w[lb] * lb_d;
        digit.emplace(lb_d);
        break;
      }
    }
    if (lb + 1 < l && digit.size() == k) ans += sum[lb + 1] * *digit.begin();
    cout << ans << '\n';
  }
  int main() {
    int t;
    cin >> t;
    while (t--) solve();
    return 0;
  }
  