#include <bits/stdc++.h>
using namespace std;
const int maxn = 500005;
const long long Mod = 998244353;
int dp[1030][12];
int a[20];
int n;
int pw[maxn];
int k;
long long dfs(int pos, long long pre, int st, int now, int fl) {
  if (pos > n) return pre;
  if (fl == 1) {
    if (now < k) {
      if (st & 1) return dfs(pos + 1, 10ll * pre, st, now, fl);
      return dfs(pos + 1, 10ll * pre, st | 1, now + 1, fl);
    }
    for (int i = 0; i <= 9; i++) {
      if (st & pw[i]) return dfs(pos + 1, 10ll * pre + i, st, now, fl);
    }
    return 1e18;
  }
  long long mn = 1e18;
  if (st & pw[a[pos]])
    mn = min(mn, dfs(pos + 1, 10ll * pre + a[pos], st, now, fl));
  else {
    if (now < k) {
      mn = min(mn,
               dfs(pos + 1, 10ll * pre + a[pos], st | pw[a[pos]], now + 1, fl));
    }
  }
  for (int i = a[pos] + 1; i <= 9; i++) {
    if (st & pw[i]) {
      mn = min(mn, dfs(pos + 1, 10ll * pre + i, st, now, 1));
      break;
    } else {
      if (now < k) {
        mn = min(mn, dfs(pos + 1, 10ll * pre + i, st | pw[i], now + 1, 1));
      }
    }
  }
  return mn;
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  ;
  pw[0] = 1;
  for (int i = 1; i <= 9; i++) pw[i] = 2 * pw[i - 1];
  int t;
  cin >> t;
  while (t--) {
    long long x;
    cin >> x >> k;
    n = 0;
    while (x) {
      a[++n] = x % 10;
      x /= 10;
    }
    reverse(a + 1, a + n + 1);
    cout << dfs(1, 0, 0, 0, 0) << endl;
  }
  return 0;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

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 maxn = 500005;
const long long Mod = 998244353;
int dp[1030][12];
int a[20];
int n;
int pw[maxn];
int k;
long long dfs(int pos, long long pre, int st, int now, int fl) {
  if (pos > n) return pre;
  if (fl == 1) {
    if (now < k) {
      if (st & 1) return dfs(pos + 1, 10ll * pre, st, now, fl);
      return dfs(pos + 1, 10ll * pre, st | 1, now + 1, fl);
    }
    for (int i = 0; i <= 9; i++) {
      if (st & pw[i]) return dfs(pos + 1, 10ll * pre + i, st, now, fl);
    }
    return 1e18;
  }
  long long mn = 1e18;
  if (st & pw[a[pos]])
    mn = min(mn, dfs(pos + 1, 10ll * pre + a[pos], st, now, fl));
  else {
    if (now < k) {
      mn = min(mn,
               dfs(pos + 1, 10ll * pre + a[pos], st | pw[a[pos]], now + 1, fl));
    }
  }
  for (int i = a[pos] + 1; i <= 9; i++) {
    if (st & pw[i]) {
      mn = min(mn, dfs(pos + 1, 10ll * pre + i, st, now, 1));
      break;
    } else {
      if (now < k) {
        mn = min(mn, dfs(pos + 1, 10ll * pre + i, st | pw[i], now + 1, 1));
      }
    }
  }
  return mn;
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  ;
  pw[0] = 1;
  for (int i = 1; i <= 9; i++) pw[i] = 2 * pw[i - 1];
  int t;
  cin >> t;
  while (t--) {
    long long x;
    cin >> x >> k;
    n = 0;
    while (x) {
      a[++n] = x % 10;
      x /= 10;
    }
    reverse(a + 1, a + n + 1);
    cout << dfs(1, 0, 0, 0, 0) << endl;
  }
  return 0;
}

```