#include <bits/stdc++.h>
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
using namespace std;
const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;
const long long INF = 0x3f3f3f3f3f3f3f3fll;
int dir[4][2] = {{1, 0}, {0, -1}, {-1, 0}, {0, 1}};
long long read() {
  long long x = 0, f = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
  return x * f;
}
void wri(long long x) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) wri(x / 10);
  putchar(x % 10 + '0');
}
void write(long long x) {
  wri(x);
  puts("");
}
long long ksc(long long a, long long b, long long mod) {
  return ((a * b -
           (long long)((long long)((long double)a / mod * b + 1e-3) * mod)) %
              mod +
          mod) %
         mod;
}
long long ksm1(long long a, long long n, long long mod) {
  long long t = 1;
  for (; n; n >>= 1, (a *= a) %= mod)
    if (n & 1) (t *= a) %= mod;
  return t;
}
long long ksm2(long long a, long long b, long long mod) {
  long long res = 1;
  while (b) {
    if (b & 1) res = ksc(res, a, mod);
    b >>= 1, a = ksc(a, a, mod);
  }
  return res % mod;
}
int is2pow(long long x) { return x > 0 ? (x & (x - 1)) == 0 : 0; }
long long myrand(long long l, long long r) {
  long long num = ((long long)rand() << 30) | ((long long)rand());
  return num % (r + 1 - l) + l;
}
const long long N = 15;
long long cnt[N];
long long last[N];
string solve(long long n) {
  string str = "";
  while (n) {
    str += n % 10 + '0';
    n /= 10;
  }
  reverse(str.begin(), str.end());
  return str;
}
signed main() {
  long long t;
  cin >> t;
  while (t--) {
    long long n, k;
    cin >> n >> k;
    memset(cnt, 0, sizeof(cnt));
    memset(last, 0, sizeof(last));
    long long geshu = 0;
    string tmp = solve(n);
    string res = "";
    long long mark = 0;
    char minn = '9';
    char maxnn = '0';
    for (long long i = 0; i < tmp.size(); i++) {
      if (geshu < k) {
        if (cnt[tmp[i] - '0'] == 0) {
          cnt[tmp[i] - '0'] = i + 1;
          last[tmp[i] - '0'] = i + 1;
          geshu++;
          res += tmp[i];
          minn = ((minn < tmp[i]) ? minn : tmp[i]);
          maxnn = ((maxnn > tmp[i]) ? maxnn : tmp[i]);
        } else
          res += tmp[i], minn = ((minn < tmp[i]) ? minn : tmp[i]),
                         last[tmp[i] - '0'] = i + 1;
      } else if (geshu == k) {
        if (mark == 0 && cnt[tmp[i] - '0'] == 0) {
          for (long long j = 0; j <= 9; j++) {
            if (cnt[j] && j >= tmp[i] - '0') {
              res += j + '0';
              mark = 1;
              break;
            }
          }
          if (mark == 0) {
            for (long long j = 0; j <= 9; j++) {
              if (cnt[j] && j > res.back() - '0') {
                res.back() = j + '0';
                res += minn;
                mark = 1;
                break;
              }
            }
          }
          if (mark == 0) {
            mark = 1;
            long long maxn = 0;
            char ch = '0';
            for (long long j = 0; j <= 9; j++) {
              if (cnt[j] > maxn) {
                maxn = cnt[j];
                ch = j + '0';
              }
            }
            long long woc = 0;
            long long wori = 0;
            for (long long i = 0; i < maxnn - '0'; i++)
              wori = ((wori > last[i]) ? wori : last[i]);
            if (wori > maxn) {
              for (long long j = 0; j <= 9; j++)
                if (cnt[j] && j > tmp[wori - 1] - '0') {
                  res[wori - 1] = j + '0';
                  mark = 1;
                  for (long long j = wori; j < i; j++) res[j] = minn;
                  res += minn;
                  woc = 1;
                  break;
                }
              if (woc) continue;
            }
            maxn--;
            if (minn == ch) minn++;
            res[maxn] = ch + 1;
            for (long long j = maxn + 1; j < i; j++) res[j] = minn;
            res += minn;
          }
        } else if (mark == 1)
          res += minn;
        else
          res += tmp[i], last[tmp[i] - '0'] = i + 1;
      }
    }
    long long pos = -1;
    for (long long i = 0; i < tmp.size(); i++) {
      if (res[i] > tmp[i]) {
        pos = i;
        break;
      }
    }
    if (pos != -1) {
      long long geshu2 = 0;
      vector<long long> vv;
      vv.clear();
      vv.resize(11);
      for (long long i = 0; i <= pos; i++) vv[res[i] - '0']++;
      for (long long i = 0; i <= 9; i++)
        if (vv[i]) geshu2++;
      if (geshu2 < k) {
        if (res[pos] != tmp[pos] + 1) {
          res[pos] = tmp[pos] + 1;
          char minn = '9';
          for (long long i = 0; i <= pos; i++)
            minn = ((minn < res[i]) ? minn : res[i]);
          for (long long i = pos + 1; i < res.size(); i++) res[i] = minn;
        } else {
          for (long long i = pos + 1; i < res.size(); i++) res[i] = '0';
        }
      }
    }
    cout << res << endl;
  }
  return 0;
}

### Prompt

Generate 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>
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
using namespace std;
const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;
const long long INF = 0x3f3f3f3f3f3f3f3fll;
int dir[4][2] = {{1, 0}, {0, -1}, {-1, 0}, {0, 1}};
long long read() {
  long long x = 0, f = 1;
  char c = getchar();
  while (c < '0' || c > '9') {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
  return x * f;
}
void wri(long long x) {
  if (x < 0) putchar('-'), x = -x;
  if (x > 9) wri(x / 10);
  putchar(x % 10 + '0');
}
void write(long long x) {
  wri(x);
  puts("");
}
long long ksc(long long a, long long b, long long mod) {
  return ((a * b -
           (long long)((long long)((long double)a / mod * b + 1e-3) * mod)) %
              mod +
          mod) %
         mod;
}
long long ksm1(long long a, long long n, long long mod) {
  long long t = 1;
  for (; n; n >>= 1, (a *= a) %= mod)
    if (n & 1) (t *= a) %= mod;
  return t;
}
long long ksm2(long long a, long long b, long long mod) {
  long long res = 1;
  while (b) {
    if (b & 1) res = ksc(res, a, mod);
    b >>= 1, a = ksc(a, a, mod);
  }
  return res % mod;
}
int is2pow(long long x) { return x > 0 ? (x & (x - 1)) == 0 : 0; }
long long myrand(long long l, long long r) {
  long long num = ((long long)rand() << 30) | ((long long)rand());
  return num % (r + 1 - l) + l;
}
const long long N = 15;
long long cnt[N];
long long last[N];
string solve(long long n) {
  string str = "";
  while (n) {
    str += n % 10 + '0';
    n /= 10;
  }
  reverse(str.begin(), str.end());
  return str;
}
signed main() {
  long long t;
  cin >> t;
  while (t--) {
    long long n, k;
    cin >> n >> k;
    memset(cnt, 0, sizeof(cnt));
    memset(last, 0, sizeof(last));
    long long geshu = 0;
    string tmp = solve(n);
    string res = "";
    long long mark = 0;
    char minn = '9';
    char maxnn = '0';
    for (long long i = 0; i < tmp.size(); i++) {
      if (geshu < k) {
        if (cnt[tmp[i] - '0'] == 0) {
          cnt[tmp[i] - '0'] = i + 1;
          last[tmp[i] - '0'] = i + 1;
          geshu++;
          res += tmp[i];
          minn = ((minn < tmp[i]) ? minn : tmp[i]);
          maxnn = ((maxnn > tmp[i]) ? maxnn : tmp[i]);
        } else
          res += tmp[i], minn = ((minn < tmp[i]) ? minn : tmp[i]),
                         last[tmp[i] - '0'] = i + 1;
      } else if (geshu == k) {
        if (mark == 0 && cnt[tmp[i] - '0'] == 0) {
          for (long long j = 0; j <= 9; j++) {
            if (cnt[j] && j >= tmp[i] - '0') {
              res += j + '0';
              mark = 1;
              break;
            }
          }
          if (mark == 0) {
            for (long long j = 0; j <= 9; j++) {
              if (cnt[j] && j > res.back() - '0') {
                res.back() = j + '0';
                res += minn;
                mark = 1;
                break;
              }
            }
          }
          if (mark == 0) {
            mark = 1;
            long long maxn = 0;
            char ch = '0';
            for (long long j = 0; j <= 9; j++) {
              if (cnt[j] > maxn) {
                maxn = cnt[j];
                ch = j + '0';
              }
            }
            long long woc = 0;
            long long wori = 0;
            for (long long i = 0; i < maxnn - '0'; i++)
              wori = ((wori > last[i]) ? wori : last[i]);
            if (wori > maxn) {
              for (long long j = 0; j <= 9; j++)
                if (cnt[j] && j > tmp[wori - 1] - '0') {
                  res[wori - 1] = j + '0';
                  mark = 1;
                  for (long long j = wori; j < i; j++) res[j] = minn;
                  res += minn;
                  woc = 1;
                  break;
                }
              if (woc) continue;
            }
            maxn--;
            if (minn == ch) minn++;
            res[maxn] = ch + 1;
            for (long long j = maxn + 1; j < i; j++) res[j] = minn;
            res += minn;
          }
        } else if (mark == 1)
          res += minn;
        else
          res += tmp[i], last[tmp[i] - '0'] = i + 1;
      }
    }
    long long pos = -1;
    for (long long i = 0; i < tmp.size(); i++) {
      if (res[i] > tmp[i]) {
        pos = i;
        break;
      }
    }
    if (pos != -1) {
      long long geshu2 = 0;
      vector<long long> vv;
      vv.clear();
      vv.resize(11);
      for (long long i = 0; i <= pos; i++) vv[res[i] - '0']++;
      for (long long i = 0; i <= 9; i++)
        if (vv[i]) geshu2++;
      if (geshu2 < k) {
        if (res[pos] != tmp[pos] + 1) {
          res[pos] = tmp[pos] + 1;
          char minn = '9';
          for (long long i = 0; i <= pos; i++)
            minn = ((minn < res[i]) ? minn : res[i]);
          for (long long i = pos + 1; i < res.size(); i++) res[i] = minn;
        } else {
          for (long long i = pos + 1; i < res.size(); i++) res[i] = '0';
        }
      }
    }
    cout << res << endl;
  }
  return 0;
}

```