#include <bits/stdc++.h>
using namespace std;
const int N = (int)5e+3 + 8;
string cal(int j, const string &n, int dist, const int &k, string nw) {
  if (dist > k) {
    return "";
  }
  if ((nw.substr(0, j)) < (n.substr(0, j))) {
    return "";
  }
  if (j >= ((int)(n).size())) {
    return nw;
  }
  for (char c = '0'; c <= '9'; c++) {
    bool found = false;
    nw[j] = c;
    for (int i = 0; i < j; i++) {
      if (nw[i] == c) {
        found = true;
        break;
      }
    }
    string ch = cal(j + 1, n, dist + (found == false), k, nw);
    if (((int)(ch).size())) return ch;
  }
  return "";
}
void MAIN(long long tc) {
  string n;
  long long k;
  cin >> n >> k;
  string ans = cal(0, n, 0, k, string(((int)(n).size()), '0'));
  cout << ans << "\n";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cout << fixed;
  cout << setprecision(10);
  int test__cases = 1;
  cin >> test__cases;
  for (int i = 1; i <= test__cases; i++) {
    MAIN(i);
  }
}

### Prompt

Develop a solution in cpp to the problem described below:

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;
const int N = (int)5e+3 + 8;
string cal(int j, const string &n, int dist, const int &k, string nw) {
  if (dist > k) {
    return "";
  }
  if ((nw.substr(0, j)) < (n.substr(0, j))) {
    return "";
  }
  if (j >= ((int)(n).size())) {
    return nw;
  }
  for (char c = '0'; c <= '9'; c++) {
    bool found = false;
    nw[j] = c;
    for (int i = 0; i < j; i++) {
      if (nw[i] == c) {
        found = true;
        break;
      }
    }
    string ch = cal(j + 1, n, dist + (found == false), k, nw);
    if (((int)(ch).size())) return ch;
  }
  return "";
}
void MAIN(long long tc) {
  string n;
  long long k;
  cin >> n >> k;
  string ans = cal(0, n, 0, k, string(((int)(n).size()), '0'));
  cout << ans << "\n";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cout << fixed;
  cout << setprecision(10);
  int test__cases = 1;
  cin >> test__cases;
  for (int i = 1; i <= test__cases; i++) {
    MAIN(i);
  }
}

```