#include <bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
template <class T>
inline bool chmax(T &a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
inline bool chmin(T &a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
struct Setup {
  Setup() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
  }
} __Setup;
using ll = long long;
const int INF = 1 << 30;
const ll LLINF = 1LL << 60;
constexpr int MOD = 1000000007;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
void Case(int i) { cout << "Case #" << i << ": "; }
int popcount(int x) { return __builtin_popcount(x); }
ll popcount(ll x) { return __builtin_popcountll(x); }
ll dp[2][1 << 10][2];
int pt[1 << 10];
void solve() {
  string N;
  int K;
  cin >> N >> K;
  int len = N.size();
  for (int i = (0); i < int(2); i++)
    for (int mask = (0); mask < int(1 << 10); mask++)
      for (int f = (0); f < int(2); f++) dp[i][mask][f] = LLINF;
  dp[0][0][0] = 0;
  int id1 = 0, id2 = 1;
  for (int i = (0); i < int(len); i++) {
    int num = N[i] - '0';
    for (int mask = (0); mask < int(1 << 10); mask++)
      for (int is_more = (0); is_more < int(2); is_more++) {
        if (dp[id1][mask][is_more] == LLINF) continue;
        for (int nxt = (0); nxt < int(10); nxt++) {
          if (i == 0 and nxt == 0) continue;
          if (!is_more and nxt < num) continue;
          int mask2 = mask | (1 << nxt);
          if (pt[mask] > K) continue;
          int is_more2 = is_more;
          if (nxt > num) is_more2 = 1;
          chmin(dp[id2][mask2][is_more2], dp[id1][mask][is_more] * 10 + nxt);
        }
        dp[id1][mask][is_more] = LLINF;
      }
    id1 ^= 1;
    id2 ^= 1;
  }
  ll ans = LLINF;
  for (int mask = (0); mask < int(1 << 10); mask++) {
    if (pt[mask] > K) continue;
    for (int f = (0); f < int(2); f++) {
      if (dp[id1][mask][f] == LLINF) continue;
      chmin(ans, dp[id1][mask][f]);
    }
  }
  cout << ans << "\n";
}
int main() {
  for (int mask = (0); mask < int(1 << 10); mask++) pt[mask] = popcount(mask);
  int T = 1;
  cin >> T;
  while (T--) solve();
}

### Prompt

Develop a solution in Cpp to the problem described below:

It is a simplified version of problem F2. 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 ≤ 2).

Output

For each test case output on a separate line x — the minimum k-beautiful integer such that x ≥ n.

Example

Input


4
1 1
221 2
177890 2
998244353 1


Output


1
221
181111
999999999

### Response

```cpp
#include <bits/stdc++.h>
#pragma GCC target("avx2")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;
template <class T>
inline bool chmax(T &a, T b) {
  if (a < b) {
    a = b;
    return 1;
  }
  return 0;
}
template <class T>
inline bool chmin(T &a, T b) {
  if (a > b) {
    a = b;
    return 1;
  }
  return 0;
}
struct Setup {
  Setup() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
  }
} __Setup;
using ll = long long;
const int INF = 1 << 30;
const ll LLINF = 1LL << 60;
constexpr int MOD = 1000000007;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
void Case(int i) { cout << "Case #" << i << ": "; }
int popcount(int x) { return __builtin_popcount(x); }
ll popcount(ll x) { return __builtin_popcountll(x); }
ll dp[2][1 << 10][2];
int pt[1 << 10];
void solve() {
  string N;
  int K;
  cin >> N >> K;
  int len = N.size();
  for (int i = (0); i < int(2); i++)
    for (int mask = (0); mask < int(1 << 10); mask++)
      for (int f = (0); f < int(2); f++) dp[i][mask][f] = LLINF;
  dp[0][0][0] = 0;
  int id1 = 0, id2 = 1;
  for (int i = (0); i < int(len); i++) {
    int num = N[i] - '0';
    for (int mask = (0); mask < int(1 << 10); mask++)
      for (int is_more = (0); is_more < int(2); is_more++) {
        if (dp[id1][mask][is_more] == LLINF) continue;
        for (int nxt = (0); nxt < int(10); nxt++) {
          if (i == 0 and nxt == 0) continue;
          if (!is_more and nxt < num) continue;
          int mask2 = mask | (1 << nxt);
          if (pt[mask] > K) continue;
          int is_more2 = is_more;
          if (nxt > num) is_more2 = 1;
          chmin(dp[id2][mask2][is_more2], dp[id1][mask][is_more] * 10 + nxt);
        }
        dp[id1][mask][is_more] = LLINF;
      }
    id1 ^= 1;
    id2 ^= 1;
  }
  ll ans = LLINF;
  for (int mask = (0); mask < int(1 << 10); mask++) {
    if (pt[mask] > K) continue;
    for (int f = (0); f < int(2); f++) {
      if (dp[id1][mask][f] == LLINF) continue;
      chmin(ans, dp[id1][mask][f]);
    }
  }
  cout << ans << "\n";
}
int main() {
  for (int mask = (0); mask < int(1 << 10); mask++) pt[mask] = popcount(mask);
  int T = 1;
  cin >> T;
  while (T--) solve();
}

```