#include <bits/stdc++.h>
using namespace std;
const long long mod = 998244353;
long long qpow(long long a, long long b) {
  a %= mod;
  long long res = 1;
  while (b) {
    if (b & 1) res = (res * a) % mod;
    a = (a * a) % mod;
    b >>= 1;
  }
  return res;
}
int a[3];
vector<long long> v1, v2;
void dfs(int m, int x, int y, long long s) {
  if (m == 12) return;
  if (a[1] > 0 && a[2] > 0) {
    v2.push_back(s);
  }
  a[1]++;
  dfs(m + 1, x, y, s * 10 + x);
  a[1]--;
  a[2]++;
  dfs(m + 1, x, y, s * 10 + y);
  a[2]--;
}
void init() {
  for (int i = 1; i <= 9; i++) {
    for (long long j = i; j <= 1e13; j = j * 10 + i) {
      v1.push_back(j);
    }
  }
  for (int i = 0; i <= 9; i++) {
    for (int j = i + 1; j <= 9; j++) {
      a[1] = a[2] = 0;
      if (i != 0)
        dfs(0, i, j, 0);
      else
        a[2]++, dfs(1, i, j, j);
    }
  }
}
void solve() {
  int n, k;
  cin >> n >> k;
  long long ans = *lower_bound(v1.begin(), v1.end(), n);
  if (k == 2)
    ans = min(ans, v2[lower_bound(v2.begin(), v2.end(), n) - v2.begin()]);
  cout << ans << endl;
}
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  init();
  sort(v1.begin(), v1.end());
  sort(v2.begin(), v2.end());
  int Case;
  cin >> Case;
  while (Case--) {
    solve();
  }
  return 0;
}

### Prompt

Create a solution in cpp for 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;
const long long mod = 998244353;
long long qpow(long long a, long long b) {
  a %= mod;
  long long res = 1;
  while (b) {
    if (b & 1) res = (res * a) % mod;
    a = (a * a) % mod;
    b >>= 1;
  }
  return res;
}
int a[3];
vector<long long> v1, v2;
void dfs(int m, int x, int y, long long s) {
  if (m == 12) return;
  if (a[1] > 0 && a[2] > 0) {
    v2.push_back(s);
  }
  a[1]++;
  dfs(m + 1, x, y, s * 10 + x);
  a[1]--;
  a[2]++;
  dfs(m + 1, x, y, s * 10 + y);
  a[2]--;
}
void init() {
  for (int i = 1; i <= 9; i++) {
    for (long long j = i; j <= 1e13; j = j * 10 + i) {
      v1.push_back(j);
    }
  }
  for (int i = 0; i <= 9; i++) {
    for (int j = i + 1; j <= 9; j++) {
      a[1] = a[2] = 0;
      if (i != 0)
        dfs(0, i, j, 0);
      else
        a[2]++, dfs(1, i, j, j);
    }
  }
}
void solve() {
  int n, k;
  cin >> n >> k;
  long long ans = *lower_bound(v1.begin(), v1.end(), n);
  if (k == 2)
    ans = min(ans, v2[lower_bound(v2.begin(), v2.end(), n) - v2.begin()]);
  cout << ans << endl;
}
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  init();
  sort(v1.begin(), v1.end());
  sort(v2.begin(), v2.end());
  int Case;
  cin >> Case;
  while (Case--) {
    solve();
  }
  return 0;
}

```