#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;
}

### Prompt

Your task is to create a CPP solution to the following problem:

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

### Response

```cpp
#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;
}

```