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

### Prompt

Please formulate 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;
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;
}

```