#include <bits/stdc++.h>
using namespace std;
int n, m, digit[30], pos, ans[30];
int use[30];
bool f;
void dfs(int p, int yu, int co, bool li) {
  if (f) return;
  if (p == 0) {
    f = true;
    return;
  }
  int i, j, k;
  if (!li) {
    for (i = digit[p]; i <= 9; i++) {
      if (i == digit[p]) {
        if (use[i] == 1) {
          ans[p] = i;
          dfs(p - 1, yu - 1, co, li);
          if (f) return;
        } else {
          if (co == 0) continue;
          ans[p] = i;
          use[i] = 1;
          dfs(p - 1, yu - 1, co - 1, li);
          use[i] = 0;
          if (f) return;
        }
      } else {
        if (use[i] == 1) {
          ans[p] = i;
          dfs(p - 1, yu - 1, co, 1);
          if (f) return;
        } else {
          if (co == 0) continue;
          ans[p] = i;
          use[i] = 1;
          dfs(p - 1, yu - 1, co - 1, 1);
          use[i] = 0;
          if (f) return;
        }
      }
    }
  } else {
    if (co == 0) {
      for (i = 0; i <= 9; i++) {
        if (use[i]) {
          ans[p] = i;
          dfs(p - 1, yu - 1, co, 1);
          if (f) return;
          break;
        }
      }
    } else {
      {
        if (use[0]) {
          ans[p] = 0;
          dfs(p - 1, yu - 1, co, 1);
          if (f) return;
        } else if (co > 0) {
          use[0] = 1;
          ans[p] = 0;
          dfs(p - 1, yu - 1, co - 1, 1);
          if (f) return;
          use[0] = 0;
        } else {
          for (i = 0; i <= 9; i++) {
            if (use[i]) {
              use[i] = 1;
              ans[p] = i;
              dfs(p - 1, yu - 1, co, 1);
              if (f) return;
              use[i] = 0;
              break;
            }
          }
        }
      }
    }
  }
}
int main() {
  int T;
  cin >> T;
  while (T--) {
    pos = 0;
    cin >> n >> m;
    int i, j, k;
    int x = n;
    while (x) {
      digit[++pos] = x % 10;
      x /= 10;
    }
    f = false;
    memset(use, 0, sizeof(use));
    dfs(pos, pos, m, 0);
    if (f) {
      for (i = pos; i >= 1; i--) printf("%d", ans[i]);
      printf("\n");
    } else {
      pos++;
      if (m == 1) {
        for (i = 1; i <= pos; i++) printf("1");
        printf("\n");
      } else {
        printf("1");
        for (i = 2; i <= pos; i++) printf("0");
        printf("\n");
      }
    }
  }
  return 0;
}

### Prompt

In CPP, your task is to solve the following problem:

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 n, m, digit[30], pos, ans[30];
int use[30];
bool f;
void dfs(int p, int yu, int co, bool li) {
  if (f) return;
  if (p == 0) {
    f = true;
    return;
  }
  int i, j, k;
  if (!li) {
    for (i = digit[p]; i <= 9; i++) {
      if (i == digit[p]) {
        if (use[i] == 1) {
          ans[p] = i;
          dfs(p - 1, yu - 1, co, li);
          if (f) return;
        } else {
          if (co == 0) continue;
          ans[p] = i;
          use[i] = 1;
          dfs(p - 1, yu - 1, co - 1, li);
          use[i] = 0;
          if (f) return;
        }
      } else {
        if (use[i] == 1) {
          ans[p] = i;
          dfs(p - 1, yu - 1, co, 1);
          if (f) return;
        } else {
          if (co == 0) continue;
          ans[p] = i;
          use[i] = 1;
          dfs(p - 1, yu - 1, co - 1, 1);
          use[i] = 0;
          if (f) return;
        }
      }
    }
  } else {
    if (co == 0) {
      for (i = 0; i <= 9; i++) {
        if (use[i]) {
          ans[p] = i;
          dfs(p - 1, yu - 1, co, 1);
          if (f) return;
          break;
        }
      }
    } else {
      {
        if (use[0]) {
          ans[p] = 0;
          dfs(p - 1, yu - 1, co, 1);
          if (f) return;
        } else if (co > 0) {
          use[0] = 1;
          ans[p] = 0;
          dfs(p - 1, yu - 1, co - 1, 1);
          if (f) return;
          use[0] = 0;
        } else {
          for (i = 0; i <= 9; i++) {
            if (use[i]) {
              use[i] = 1;
              ans[p] = i;
              dfs(p - 1, yu - 1, co, 1);
              if (f) return;
              use[i] = 0;
              break;
            }
          }
        }
      }
    }
  }
}
int main() {
  int T;
  cin >> T;
  while (T--) {
    pos = 0;
    cin >> n >> m;
    int i, j, k;
    int x = n;
    while (x) {
      digit[++pos] = x % 10;
      x /= 10;
    }
    f = false;
    memset(use, 0, sizeof(use));
    dfs(pos, pos, m, 0);
    if (f) {
      for (i = pos; i >= 1; i--) printf("%d", ans[i]);
      printf("\n");
    } else {
      pos++;
      if (m == 1) {
        for (i = 1; i <= pos; i++) printf("1");
        printf("\n");
      } else {
        printf("1");
        for (i = 2; i <= pos; i++) printf("0");
        printf("\n");
      }
    }
  }
  return 0;
}

```