#include <bits/stdc++.h>
using namespace std;
const long long INF = 0x7fffffffffffffff;
const long long MAXN = 2e5 + 9;
void fast_stream() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
}
long long len(long long n) {
  if (n == 0) return 1;
  long long ans = 0;
  while (n > 0) ans++, n /= 10;
  return ans;
}
long long lft(long long p, long long l1, long long l2) {
  long long l = l1 - l2;
  while (l--) p *= 10;
  return p;
}
long long rgh(long long k0, long long l) {
  long long res = 0;
  while (l--) res = 10 * res + k0;
  return res;
}
long long Ans, t;
void dfs(long long n, long long p, long long k1, long long k2, long long l1,
         long long l2) {
  if (lft(p, l1, l2) > Ans || lft(p, l1, l2) + rgh(max(k1, k2), l1 - l2) < p)
    return;
  if (l1 == l2) {
    if (p >= n) Ans = min(Ans, p);
    return;
  }
  if (!(l2 == 0 && k1 == 0)) dfs(n, 10 * p + k1, k1, k2, l1, l2 + 1);
  if (!(l2 == 0 && k2 == 0)) dfs(n, 10 * p + k2, k1, k2, l1, l2 + 1);
}
void solve() {
  long long n, k;
  scanf("%lld%lld", &n, &k);
  long long lenN = len(n);
  Ans = INF;
  for (long long k1 = 0; k1 <= 9; k1++) {
    for (long long k2 = k1; k2 <= 9; k2++) {
      if (k == 1 && k1 != k2) continue;
      if (rgh(max(k2, k1), lenN) < n) continue;
      if (rgh(min(k1, k2), lenN) > Ans) continue;
      dfs(n, 0, k1, k2, lenN, 0);
    }
  }
  printf("%d\n", Ans);
}
signed main() {
  fast_stream();
  scanf("%lld", &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>
using namespace std;
const long long INF = 0x7fffffffffffffff;
const long long MAXN = 2e5 + 9;
void fast_stream() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
}
long long len(long long n) {
  if (n == 0) return 1;
  long long ans = 0;
  while (n > 0) ans++, n /= 10;
  return ans;
}
long long lft(long long p, long long l1, long long l2) {
  long long l = l1 - l2;
  while (l--) p *= 10;
  return p;
}
long long rgh(long long k0, long long l) {
  long long res = 0;
  while (l--) res = 10 * res + k0;
  return res;
}
long long Ans, t;
void dfs(long long n, long long p, long long k1, long long k2, long long l1,
         long long l2) {
  if (lft(p, l1, l2) > Ans || lft(p, l1, l2) + rgh(max(k1, k2), l1 - l2) < p)
    return;
  if (l1 == l2) {
    if (p >= n) Ans = min(Ans, p);
    return;
  }
  if (!(l2 == 0 && k1 == 0)) dfs(n, 10 * p + k1, k1, k2, l1, l2 + 1);
  if (!(l2 == 0 && k2 == 0)) dfs(n, 10 * p + k2, k1, k2, l1, l2 + 1);
}
void solve() {
  long long n, k;
  scanf("%lld%lld", &n, &k);
  long long lenN = len(n);
  Ans = INF;
  for (long long k1 = 0; k1 <= 9; k1++) {
    for (long long k2 = k1; k2 <= 9; k2++) {
      if (k == 1 && k1 != k2) continue;
      if (rgh(max(k2, k1), lenN) < n) continue;
      if (rgh(min(k1, k2), lenN) > Ans) continue;
      dfs(n, 0, k1, k2, lenN, 0);
    }
  }
  printf("%d\n", Ans);
}
signed main() {
  fast_stream();
  scanf("%lld", &t);
  while (t--) {
    solve();
  }
}

```