#include <bits/stdc++.h>
using namespace std;
template <typename T1>
void dbg_pr(vector<T1> V, int add = 0, int start = -1, int end = -1) {
  cout << "{";
  if (start < 0) start = 0;
  if (end < 0) end = V.size() - 1;
  for (int i = start; i <= end; i++) {
    cout << V[i] + add << ((i == end) ? "}" : " ");
  }
}
void dbg_pr(string V) { cout << "\"" << V << "\""; }
template <typename T1>
void dbg_pr(T1 V) {
  cout << V;
}
template <typename T1, typename T2>
void dbg_pr(map<T1, T2> M) {
  cout << "{";
  for (const auto m : M) {
    dbg_pr(m.first);
    cout << ":";
    dbg_pr(m.second);
    cout << ",";
  }
  cout << "}";
}
void debug_out() { cout << "\033[0m\n"; }
template <typename T1, typename... T2>
void debug_out(T1 A, T2... B) {
  cout << " ";
  dbg_pr(A);
  debug_out(B...);
}
int test = 1;
void setupFastCin() {
  ios::sync_with_stdio(false);
  cin.tie(0);
}
template <typename T1>
T1 chmin(T1 &x, const T1 v) {
  return x = min(x, v);
}
template <typename T1>
T1 chmax(T1 &x, const T1 v) {
  return x = max(x, v);
}
template <typename T1>
void pr(vector<T1> V, int add = 0, int start = -1, int end = -1) {
  if (start < 0) start = 0;
  if (end < 0) end = V.size() - 1;
  for (int i = start; i <= end; i++) {
    cout << V[i] + add << ((i == end) ? "\n" : " ");
  }
}
template <typename T1>
T1 gcd(const T1 &a, const T1 &b) {
  if (a == 0 || b == 0) return a + b;
  return gcd(b, a % b);
}
int K;
string S;
long long DP[11][2000][2];
long long dp(int i, int mask, int k, int comp, long long p) {
  if (k > K) return LLONG_MAX;
  if (i == S.size()) {
    return 0;
  }
  if (DP[i][mask][comp] != -1) return DP[i][mask][comp];
  int md = S[i] - '0';
  long long sol = LLONG_MAX;
  for (int d = 0; d < 10; d++) {
    if (comp == 0 && d < md) continue;
    int newMask = mask;
    int newK = k;
    if ((mask & (1 << d)) == 0) {
      newMask += (1 << d);
      newK++;
    }
    if (newK > K) continue;
    int newC = comp;
    if (comp == 0) newC = d > md ? 1 : 0;
    long long s = dp(i + 1, newMask, newK, newC, p / 10);
    if (s == LLONG_MAX) continue;
    chmin(sol, d * p + s);
    break;
  }
  return DP[i][mask][comp] = sol;
}
void solve() {
  for (int i = 0; i < 11; i++)
    for (int j = 0; j < 1025; j++) DP[i][j][0] = DP[i][j][1] = -1;
  cin >> S >> K;
  long long p = pow(10ll, S.size() - 1);
  {
    cout << dp(0, 0, 0, 0, p) << "\n";
    return;
  };
}
int main() {
  setupFastCin();
  int T = 1;
  cin >> T;
  for (int t = 0; t < T; t++) {
    solve();
  }
  return 0;
}

### Prompt

Your challenge is to write 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;
template <typename T1>
void dbg_pr(vector<T1> V, int add = 0, int start = -1, int end = -1) {
  cout << "{";
  if (start < 0) start = 0;
  if (end < 0) end = V.size() - 1;
  for (int i = start; i <= end; i++) {
    cout << V[i] + add << ((i == end) ? "}" : " ");
  }
}
void dbg_pr(string V) { cout << "\"" << V << "\""; }
template <typename T1>
void dbg_pr(T1 V) {
  cout << V;
}
template <typename T1, typename T2>
void dbg_pr(map<T1, T2> M) {
  cout << "{";
  for (const auto m : M) {
    dbg_pr(m.first);
    cout << ":";
    dbg_pr(m.second);
    cout << ",";
  }
  cout << "}";
}
void debug_out() { cout << "\033[0m\n"; }
template <typename T1, typename... T2>
void debug_out(T1 A, T2... B) {
  cout << " ";
  dbg_pr(A);
  debug_out(B...);
}
int test = 1;
void setupFastCin() {
  ios::sync_with_stdio(false);
  cin.tie(0);
}
template <typename T1>
T1 chmin(T1 &x, const T1 v) {
  return x = min(x, v);
}
template <typename T1>
T1 chmax(T1 &x, const T1 v) {
  return x = max(x, v);
}
template <typename T1>
void pr(vector<T1> V, int add = 0, int start = -1, int end = -1) {
  if (start < 0) start = 0;
  if (end < 0) end = V.size() - 1;
  for (int i = start; i <= end; i++) {
    cout << V[i] + add << ((i == end) ? "\n" : " ");
  }
}
template <typename T1>
T1 gcd(const T1 &a, const T1 &b) {
  if (a == 0 || b == 0) return a + b;
  return gcd(b, a % b);
}
int K;
string S;
long long DP[11][2000][2];
long long dp(int i, int mask, int k, int comp, long long p) {
  if (k > K) return LLONG_MAX;
  if (i == S.size()) {
    return 0;
  }
  if (DP[i][mask][comp] != -1) return DP[i][mask][comp];
  int md = S[i] - '0';
  long long sol = LLONG_MAX;
  for (int d = 0; d < 10; d++) {
    if (comp == 0 && d < md) continue;
    int newMask = mask;
    int newK = k;
    if ((mask & (1 << d)) == 0) {
      newMask += (1 << d);
      newK++;
    }
    if (newK > K) continue;
    int newC = comp;
    if (comp == 0) newC = d > md ? 1 : 0;
    long long s = dp(i + 1, newMask, newK, newC, p / 10);
    if (s == LLONG_MAX) continue;
    chmin(sol, d * p + s);
    break;
  }
  return DP[i][mask][comp] = sol;
}
void solve() {
  for (int i = 0; i < 11; i++)
    for (int j = 0; j < 1025; j++) DP[i][j][0] = DP[i][j][1] = -1;
  cin >> S >> K;
  long long p = pow(10ll, S.size() - 1);
  {
    cout << dp(0, 0, 0, 0, p) << "\n";
    return;
  };
}
int main() {
  setupFastCin();
  int T = 1;
  cin >> T;
  for (int t = 0; t < T; t++) {
    solve();
  }
  return 0;
}

```