#include <bits/stdc++.h>
using namespace std;
int T;
long long n, k, p, ans, sum, bit[10];
bool sol, over;
void dfs(int now, int Pow) {
  if (!Pow) {
    sol = true;
    return;
  }
  long long num = now / Pow, add = 0;
  if (over) {
    if (bit[0]) {
      bit[0]++;
      dfs(now % Pow, Pow / 10);
    } else {
      if (sum < k) {
        sum++;
        bit[0]++;
        dfs(now % Pow, Pow / 10);
      } else {
        int low = -1;
        for (int i = 1; i < 10; i++)
          if (bit[i]) {
            low = i;
            break;
          }
        bit[low]++;
        dfs(now % Pow, Pow / 10);
        ans += low * Pow;
      }
    }
    return;
  }
  if (sum < k) {
    add = num * Pow;
    if (!bit[num]) sum++;
    bit[num]++;
    dfs(now % Pow, Pow / 10);
    if (sol) {
      ans += add;
      return;
    }
    bit[num]--;
    ans %= Pow;
    if (!bit[num]) sum--;
    if (num == 9) return;
    add += Pow;
    if (!bit[num + 1]) sum++;
    bit[num + 1]++;
    over = true;
    dfs(now % Pow, Pow / 10);
    ans += add;
  } else {
    if (bit[num]) {
      add = num * Pow;
      bit[num]++;
      dfs(now % Pow, Pow / 10);
      if (sol) {
        ans += add;
        return;
      }
      ans %= Pow;
      bit[num]--;
    }
    int low = -1;
    for (int i = num + 1; i < 10; i++)
      if (bit[i]) {
        low = i;
        break;
      }
    if (low == -1) return;
    bit[low]++;
    add = low * Pow;
    over = true;
    dfs(now % Pow, Pow / 10);
    ans += add;
  }
}
int main() {
  scanf("%d", &T);
  while (T--) {
    p = 1;
    ans = sum = 0;
    memset(bit, 0, sizeof(bit));
    over = sol = false;
    scanf("%lld%lld", &n, &k);
    while (n / p) p *= 10;
    dfs(n, p / 10);
    printf("%d\n", ans);
  }
  return 0;
}

### Prompt

Please provide a cpp coded solution 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>
using namespace std;
int T;
long long n, k, p, ans, sum, bit[10];
bool sol, over;
void dfs(int now, int Pow) {
  if (!Pow) {
    sol = true;
    return;
  }
  long long num = now / Pow, add = 0;
  if (over) {
    if (bit[0]) {
      bit[0]++;
      dfs(now % Pow, Pow / 10);
    } else {
      if (sum < k) {
        sum++;
        bit[0]++;
        dfs(now % Pow, Pow / 10);
      } else {
        int low = -1;
        for (int i = 1; i < 10; i++)
          if (bit[i]) {
            low = i;
            break;
          }
        bit[low]++;
        dfs(now % Pow, Pow / 10);
        ans += low * Pow;
      }
    }
    return;
  }
  if (sum < k) {
    add = num * Pow;
    if (!bit[num]) sum++;
    bit[num]++;
    dfs(now % Pow, Pow / 10);
    if (sol) {
      ans += add;
      return;
    }
    bit[num]--;
    ans %= Pow;
    if (!bit[num]) sum--;
    if (num == 9) return;
    add += Pow;
    if (!bit[num + 1]) sum++;
    bit[num + 1]++;
    over = true;
    dfs(now % Pow, Pow / 10);
    ans += add;
  } else {
    if (bit[num]) {
      add = num * Pow;
      bit[num]++;
      dfs(now % Pow, Pow / 10);
      if (sol) {
        ans += add;
        return;
      }
      ans %= Pow;
      bit[num]--;
    }
    int low = -1;
    for (int i = num + 1; i < 10; i++)
      if (bit[i]) {
        low = i;
        break;
      }
    if (low == -1) return;
    bit[low]++;
    add = low * Pow;
    over = true;
    dfs(now % Pow, Pow / 10);
    ans += add;
  }
}
int main() {
  scanf("%d", &T);
  while (T--) {
    p = 1;
    ans = sum = 0;
    memset(bit, 0, sizeof(bit));
    over = sol = false;
    scanf("%lld%lld", &n, &k);
    while (n / p) p *= 10;
    dfs(n, p / 10);
    printf("%d\n", ans);
  }
  return 0;
}

```