#include <bits/stdc++.h>
using namespace std;
long long mod = 1000000007;
bool sortbysec(const pair<long long, long long> &a,
               const pair<long long, long long> &b) {
  return (a.second < b.second);
}
long long gcdExtended(long long a, long long b, long long *x, long long *y) {
  if (a == 0) {
    *x = 0, *y = 1;
    return b;
  }
  long long x1, y1;
  long long gcd = gcdExtended(b % a, a, &x1, &y1);
  *x = y1 - (b / a) * x1;
  *y = x1;
  return gcd;
}
bool isSubstring(string s1, string s2) {
  long long M = s1.length();
  long long N = s2.length();
  for (long long i = 0; i <= N - M; i++) {
    long long j;
    for (j = 0; j < M; j++)
      if (s2[i + j] != s1[j]) break;
    if (j == M) return 1;
  }
  return 0;
}
long long gcd(long long a, long long b) {
  while (b > 0) {
    long long p = a % b;
    a = b;
    b = p;
  }
  return a;
}
long long binpow(long long b) {
  long long m = mod;
  long long a = 2;
  a %= m;
  long long res = 1;
  while (b > 0) {
    if (b & 1) {
      res = (res * a) % m;
    }
    a = (a * a) % m;
    b >>= 1;
  }
  return res;
}
const long long xx = 1e3 + 5;
vector<long long> index1(xx + 1), index2(xx + 1), par1(xx + 1), par2(xx + 1);
long long find_par(long long a, vector<long long> &par) {
  if (a == par[a]) return a;
  return par[a] = find_par(par[a], par);
}
void make_union(long long a, long long b, vector<long long> &par,
                vector<long long> &index) {
  long long p1 = find_par(a, par);
  long long p2 = find_par(b, par);
  if (p1 != p2) {
    long long ma = max(p1, p2);
    long long mi = p2 + p1 - ma;
    par[mi] = ma;
    index[ma]++;
  }
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long t;
  cin >> t;
  long long k, n, m1, m2, q;
  string a, a1, a2;
  for (long long i = 0; i < t; i++) {
    cin >> a >> k;
    if (k == 1) {
      bool ch = false;
      char temp = a[0];
      long long ke = -1;
      for (long long j = 0; j < a.length(); j++) {
        if (a[j] != temp) {
          ke = j;
          break;
        }
      }
      if (ke != -1) {
        if (a[ke] > a[0]) {
          a[0]++;
          for (long long j = 0; j < a.length(); j++) {
            cout << (a[0]);
          }
        } else {
          for (long long j = 0; j < a.length(); j++) {
            cout << a[0];
          }
        }
        cout << "\n";
        continue;
      } else {
        cout << a << "\n";
      }
    }
    if (k >= 2) {
      vector<char> v;
      map<char, long long> m;
      long long p1 = 0;
      set<char> s;
      bool ch = 0;
      bool det;
      long long ke = -1;
      for (long long j = 0; j < a.length(); j++) {
        s.insert((a[j]));
        if (p1 != s.size()) {
          if (ch == 0) {
            v.push_back((a[j]));
            sort(v.begin(), v.end());
            p1++;
            m[a[j]] = j;
            if (v.size() == k) {
              ch = 1;
            }
          } else {
            ke = j;
            if (a[j] > v[v.size() - 1]) {
              det = 1;
              break;
            } else {
              det = 0;
              break;
            }
          }
        }
      }
      if (ke == -1) {
        cout << a << "\n";
        continue;
      }
      string ans = "";
      char mid;
      if (det == 0) {
        for (long long j = 0; j < v.size(); j++) {
          if (v[j] > a[ke]) {
            mid = v[j];
            break;
          }
        }
        for (long long j = 0; j < ke; j++) {
          ans += a[j];
        }
        ans += mid;
        for (long long j = ke + 1; j < a.length(); j++) {
          ans += v[0];
        }
      } else {
        if (a[ke - 1] != v[v.size() - 1]) {
          for (long long j = 0; j < v.size(); j++) {
            if (v[j] > a[ke - 1]) {
              mid = v[j];
              break;
            }
          }
          for (long long j = 0; j < ke - 1; j++) {
            ans += a[j];
          }
          ans += mid;
          for (long long j = ke; j < a.length(); j++) {
            ans += v[0];
          }
          if (m[a[ke - 1]] == ke - 1) {
            ans = "";
            char ex = a[ke - 1];
            ex++;
            for (long long j = 0; j < ke - 1; j++) {
              ans += a[j];
            }
            ans += ex;
            long long ex1;
            long long foun = -1;
            for (long long j = 0; j < v.size(); j++) {
              if (v[j] == ex) {
                foun = j;
                break;
              }
            }
            if (v[0] == a[ke - 1]) {
              ex1 = ex;
            } else {
              ex1 = v[0];
            }
            if (ex1 == v[1]) {
              ex1 = v[0];
            }
            if (foun != -1) {
              ex1 = '0';
            }
            for (long long j = ke; j < a.length(); j++) {
              ans += ex1;
            }
          }
        } else {
          long long st;
          for (long long j = ke - 1; j >= 0; j--) {
            if (a[j] < a[ke - 1]) {
              st = j;
              break;
            }
          }
          if (st < m[a[ke - 1]]) {
            for (long long j = 0; j <= st; j++) {
              ans += a[j];
            }
            char ex = a[ke - 1];
            ex++;
            ans += ex;
            for (long long j = st + 2; j < a.length(); j++) {
              ans += v[0];
            }
          } else {
            for (long long j = 0; j < v.size(); j++) {
              if (v[j] > a[st]) {
                mid = v[j];
                break;
              }
            }
            for (long long j = 0; j < st; j++) {
              ans += a[j];
            }
            ans += mid;
            for (long long j = st + 1; j < a.length(); j++) {
              ans += v[0];
            }
            if (m[a[st]] == st) {
              ans = "";
              char ex = a[st];
              ex++;
              char ex1;
              long long foun = -1;
              for (long long j = 0; j < v.size(); j++) {
                if (v[j] == ex) {
                  foun = j;
                  break;
                }
              }
              for (long long j = 0; j < st; j++) {
                ans += a[j];
              }
              ans += ex;
              if (foun == -1) {
                if (v[0] != a[st]) {
                  ex1 = min(ex, v[0]);
                } else {
                  ex1 = min(ex, v[1]);
                }
              } else {
                ex1 = '0';
              }
              for (long long j = st + 1; j < a.length(); j++) {
                ans += ex1;
              }
            }
          }
        }
      }
      cout << ans << "\n";
    }
  }
}

### 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;
long long mod = 1000000007;
bool sortbysec(const pair<long long, long long> &a,
               const pair<long long, long long> &b) {
  return (a.second < b.second);
}
long long gcdExtended(long long a, long long b, long long *x, long long *y) {
  if (a == 0) {
    *x = 0, *y = 1;
    return b;
  }
  long long x1, y1;
  long long gcd = gcdExtended(b % a, a, &x1, &y1);
  *x = y1 - (b / a) * x1;
  *y = x1;
  return gcd;
}
bool isSubstring(string s1, string s2) {
  long long M = s1.length();
  long long N = s2.length();
  for (long long i = 0; i <= N - M; i++) {
    long long j;
    for (j = 0; j < M; j++)
      if (s2[i + j] != s1[j]) break;
    if (j == M) return 1;
  }
  return 0;
}
long long gcd(long long a, long long b) {
  while (b > 0) {
    long long p = a % b;
    a = b;
    b = p;
  }
  return a;
}
long long binpow(long long b) {
  long long m = mod;
  long long a = 2;
  a %= m;
  long long res = 1;
  while (b > 0) {
    if (b & 1) {
      res = (res * a) % m;
    }
    a = (a * a) % m;
    b >>= 1;
  }
  return res;
}
const long long xx = 1e3 + 5;
vector<long long> index1(xx + 1), index2(xx + 1), par1(xx + 1), par2(xx + 1);
long long find_par(long long a, vector<long long> &par) {
  if (a == par[a]) return a;
  return par[a] = find_par(par[a], par);
}
void make_union(long long a, long long b, vector<long long> &par,
                vector<long long> &index) {
  long long p1 = find_par(a, par);
  long long p2 = find_par(b, par);
  if (p1 != p2) {
    long long ma = max(p1, p2);
    long long mi = p2 + p1 - ma;
    par[mi] = ma;
    index[ma]++;
  }
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long t;
  cin >> t;
  long long k, n, m1, m2, q;
  string a, a1, a2;
  for (long long i = 0; i < t; i++) {
    cin >> a >> k;
    if (k == 1) {
      bool ch = false;
      char temp = a[0];
      long long ke = -1;
      for (long long j = 0; j < a.length(); j++) {
        if (a[j] != temp) {
          ke = j;
          break;
        }
      }
      if (ke != -1) {
        if (a[ke] > a[0]) {
          a[0]++;
          for (long long j = 0; j < a.length(); j++) {
            cout << (a[0]);
          }
        } else {
          for (long long j = 0; j < a.length(); j++) {
            cout << a[0];
          }
        }
        cout << "\n";
        continue;
      } else {
        cout << a << "\n";
      }
    }
    if (k >= 2) {
      vector<char> v;
      map<char, long long> m;
      long long p1 = 0;
      set<char> s;
      bool ch = 0;
      bool det;
      long long ke = -1;
      for (long long j = 0; j < a.length(); j++) {
        s.insert((a[j]));
        if (p1 != s.size()) {
          if (ch == 0) {
            v.push_back((a[j]));
            sort(v.begin(), v.end());
            p1++;
            m[a[j]] = j;
            if (v.size() == k) {
              ch = 1;
            }
          } else {
            ke = j;
            if (a[j] > v[v.size() - 1]) {
              det = 1;
              break;
            } else {
              det = 0;
              break;
            }
          }
        }
      }
      if (ke == -1) {
        cout << a << "\n";
        continue;
      }
      string ans = "";
      char mid;
      if (det == 0) {
        for (long long j = 0; j < v.size(); j++) {
          if (v[j] > a[ke]) {
            mid = v[j];
            break;
          }
        }
        for (long long j = 0; j < ke; j++) {
          ans += a[j];
        }
        ans += mid;
        for (long long j = ke + 1; j < a.length(); j++) {
          ans += v[0];
        }
      } else {
        if (a[ke - 1] != v[v.size() - 1]) {
          for (long long j = 0; j < v.size(); j++) {
            if (v[j] > a[ke - 1]) {
              mid = v[j];
              break;
            }
          }
          for (long long j = 0; j < ke - 1; j++) {
            ans += a[j];
          }
          ans += mid;
          for (long long j = ke; j < a.length(); j++) {
            ans += v[0];
          }
          if (m[a[ke - 1]] == ke - 1) {
            ans = "";
            char ex = a[ke - 1];
            ex++;
            for (long long j = 0; j < ke - 1; j++) {
              ans += a[j];
            }
            ans += ex;
            long long ex1;
            long long foun = -1;
            for (long long j = 0; j < v.size(); j++) {
              if (v[j] == ex) {
                foun = j;
                break;
              }
            }
            if (v[0] == a[ke - 1]) {
              ex1 = ex;
            } else {
              ex1 = v[0];
            }
            if (ex1 == v[1]) {
              ex1 = v[0];
            }
            if (foun != -1) {
              ex1 = '0';
            }
            for (long long j = ke; j < a.length(); j++) {
              ans += ex1;
            }
          }
        } else {
          long long st;
          for (long long j = ke - 1; j >= 0; j--) {
            if (a[j] < a[ke - 1]) {
              st = j;
              break;
            }
          }
          if (st < m[a[ke - 1]]) {
            for (long long j = 0; j <= st; j++) {
              ans += a[j];
            }
            char ex = a[ke - 1];
            ex++;
            ans += ex;
            for (long long j = st + 2; j < a.length(); j++) {
              ans += v[0];
            }
          } else {
            for (long long j = 0; j < v.size(); j++) {
              if (v[j] > a[st]) {
                mid = v[j];
                break;
              }
            }
            for (long long j = 0; j < st; j++) {
              ans += a[j];
            }
            ans += mid;
            for (long long j = st + 1; j < a.length(); j++) {
              ans += v[0];
            }
            if (m[a[st]] == st) {
              ans = "";
              char ex = a[st];
              ex++;
              char ex1;
              long long foun = -1;
              for (long long j = 0; j < v.size(); j++) {
                if (v[j] == ex) {
                  foun = j;
                  break;
                }
              }
              for (long long j = 0; j < st; j++) {
                ans += a[j];
              }
              ans += ex;
              if (foun == -1) {
                if (v[0] != a[st]) {
                  ex1 = min(ex, v[0]);
                } else {
                  ex1 = min(ex, v[1]);
                }
              } else {
                ex1 = '0';
              }
              for (long long j = st + 1; j < a.length(); j++) {
                ans += ex1;
              }
            }
          }
        }
      }
      cout << ans << "\n";
    }
  }
}

```