#include <bits/stdc++.h>
using namespace std;
int a[20];
int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    long long n, k;
    cin >> n >> k;
    vector<int> v;
    int y = n;
    while (y) {
      v.push_back(y % 10);
      y /= 10;
    }
    reverse(v.begin(), v.end());
    int sz = v.size();
    if (k == 1) {
      bool les = 0, bg = 0;
      for (int i = 1; i < sz; i++) {
        if (v[i] < v[0])
          les = 1;
        else if (v[i] > v[0]) {
          bg = 1;
          break;
        }
      }
      if (!les && bg)
        for (int i = 0; i < sz; i++) a[i] = v[0] + 1;
      else
        for (int i = 0; i < sz; i++) a[i] = v[0];
      for (int i = 0; i < sz; i++) cout << a[i];
      cout << '\n';
      continue;
    }
    int cnt[11] = {0};
    int cc = 0;
    for (auto i : v)
      if (!cnt[i]) cc++, cnt[i]++;
    if (cc <= k) {
      cout << n << '\n';
      continue;
    }
    for (int i = 0; i < 10; i++) cnt[i] = 0;
    cc = 0;
    int mn = 10, mx = -1;
    for (int i = 0; i < sz; i++) {
      int x = v[i];
      if (!cnt[x]) {
        cc++;
      }
      if (cc > k) {
        if (x > mx) {
          int sum = 0;
          for (int j = i - 1; j >= 0; j--) {
            if (v[j] != mx) break;
            sum++;
          }
          if (sum == cnt[mx]) {
            for (int j = i - 1; j >= 0; j--) {
              if (v[j] == mx)
                a[j] = mn;
              else {
                a[j + 1] = mx + 1;
                break;
              }
            }
            for (int j = i; j < sz; j++) a[j] = mn;
          } else {
            for (int j = i - 1; j >= 0; j--) {
              if (v[j] != mx) {
                int y, nx;
                if (cnt[v[j]] == 1) {
                  y = v[j] + 1, nx;
                  if (cnt[y]) {
                    nx = 0;
                  } else {
                    if (v[j] == mn)
                      nx = y;
                    else
                      nx = mn;
                  }
                } else {
                  for (y = v[j] + 1; y < 10; y++) {
                    if (cnt[y]) break;
                  }
                  nx = mn;
                }
                a[j] = y;
                for (int q = j + 1; q < sz; q++) {
                  a[q] = nx;
                }
                break;
              }
            }
          }
        } else {
          for (int j = x + 1; j < 10; j++) {
            if (cnt[j]) {
              a[i] = j;
              break;
            }
          }
          for (int j = i + 1; j < sz; j++) a[j] = mn;
        }
        break;
      }
      a[i] = x;
      cnt[x]++;
      mn = min(mn, x), mx = max(mx, x);
    }
    for (int i = 0; i < sz; i++) cout << a[i];
    cout << '\n';
  }
  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;
int a[20];
int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    long long n, k;
    cin >> n >> k;
    vector<int> v;
    int y = n;
    while (y) {
      v.push_back(y % 10);
      y /= 10;
    }
    reverse(v.begin(), v.end());
    int sz = v.size();
    if (k == 1) {
      bool les = 0, bg = 0;
      for (int i = 1; i < sz; i++) {
        if (v[i] < v[0])
          les = 1;
        else if (v[i] > v[0]) {
          bg = 1;
          break;
        }
      }
      if (!les && bg)
        for (int i = 0; i < sz; i++) a[i] = v[0] + 1;
      else
        for (int i = 0; i < sz; i++) a[i] = v[0];
      for (int i = 0; i < sz; i++) cout << a[i];
      cout << '\n';
      continue;
    }
    int cnt[11] = {0};
    int cc = 0;
    for (auto i : v)
      if (!cnt[i]) cc++, cnt[i]++;
    if (cc <= k) {
      cout << n << '\n';
      continue;
    }
    for (int i = 0; i < 10; i++) cnt[i] = 0;
    cc = 0;
    int mn = 10, mx = -1;
    for (int i = 0; i < sz; i++) {
      int x = v[i];
      if (!cnt[x]) {
        cc++;
      }
      if (cc > k) {
        if (x > mx) {
          int sum = 0;
          for (int j = i - 1; j >= 0; j--) {
            if (v[j] != mx) break;
            sum++;
          }
          if (sum == cnt[mx]) {
            for (int j = i - 1; j >= 0; j--) {
              if (v[j] == mx)
                a[j] = mn;
              else {
                a[j + 1] = mx + 1;
                break;
              }
            }
            for (int j = i; j < sz; j++) a[j] = mn;
          } else {
            for (int j = i - 1; j >= 0; j--) {
              if (v[j] != mx) {
                int y, nx;
                if (cnt[v[j]] == 1) {
                  y = v[j] + 1, nx;
                  if (cnt[y]) {
                    nx = 0;
                  } else {
                    if (v[j] == mn)
                      nx = y;
                    else
                      nx = mn;
                  }
                } else {
                  for (y = v[j] + 1; y < 10; y++) {
                    if (cnt[y]) break;
                  }
                  nx = mn;
                }
                a[j] = y;
                for (int q = j + 1; q < sz; q++) {
                  a[q] = nx;
                }
                break;
              }
            }
          }
        } else {
          for (int j = x + 1; j < 10; j++) {
            if (cnt[j]) {
              a[i] = j;
              break;
            }
          }
          for (int j = i + 1; j < sz; j++) a[j] = mn;
        }
        break;
      }
      a[i] = x;
      cnt[x]++;
      mn = min(mn, x), mx = max(mx, x);
    }
    for (int i = 0; i < sz; i++) cout << a[i];
    cout << '\n';
  }
  return 0;
}

```