#include <bits/stdc++.h>
using namespace std;
const long double Pi = acos(-1);
string add(string a, string b) {
  string result = "";
  int temp = 0;
  int size_a = a.size() - 1;
  int size_b = b.size() - 1;
  while (size_a >= 0 || size_b >= 0 || temp == 1) {
    temp += ((size_a >= 0) ? a[size_a] - '0' : 0);
    temp += ((size_b >= 0) ? b[size_b] - '0' : 0);
    result = char(temp % 2 + '0') + result;
    temp /= 2;
    size_a--;
    size_b--;
  }
  return result;
}
string decimalToBinary(int n) {
  string s = bitset<64>(n).to_string();
  const auto loc1 = s.find('1');
  if (loc1 != string::npos) return s.substr(loc1);
  return "0";
}
int nofdigits(int n) {
  int coun = 0;
  while (n != 0) {
    n = n / 10;
    coun++;
  }
  return coun;
}
void solve() {
  int n, k;
  cin >> n >> k;
  int num = n;
  vector<int> v;
  while (num != 0) {
    v.push_back(num % 10);
    num = num / 10;
  }
  reverse(v.begin(), v.end());
  if (k == 1) {
    int dif[2];
    memset(dif, -1, sizeof(dif));
    int number_of_digits = nofdigits(n);
    dif[0] = n / pow(10, number_of_digits - 1);
    for (int i = number_of_digits - 2; i > -1; i--) {
      int tmp = n / pow(10, i);
      if (tmp % 10 != dif[0]) {
        dif[1] = tmp % 10;
        break;
      }
    }
    if (dif[1] == -1)
      cout << n << "\n";
    else {
      if (dif[1] < dif[0]) {
        for (int i = 0; i < number_of_digits; i++) cout << dif[0];
      } else {
        for (int i = 0; i < number_of_digits; i++) cout << (dif[0] + 1);
      }
      cout << "\n";
    }
  }
  if (k == 2) {
    int dif[10];
    memset(dif, -1, sizeof(dif));
    int number_of_digits = nofdigits(n);
    dif[0] = n / pow(10, number_of_digits - 1);
    int pos[10];
    int curr = 0;
    for (int i = number_of_digits - 2; i > -1; i--) {
      int tmp = n / pow(10, i);
      if (tmp % 10 != dif[curr] && tmp % 10 != dif[0]) {
        dif[curr + 1] = tmp % 10;
        pos[curr] = number_of_digits - i - 1;
        curr++;
      }
    }
    if (dif[2] == -1)
      cout << n << "\n";
    else {
      string original_num = to_string(n);
      string current_num = original_num.substr(0, pos[0]);
      current_num = current_num + to_string(dif[1]);
      string right_part = "";
      string full_num = "";
      int a = min(dif[0], dif[1]);
      int b = max(dif[0], dif[1]);
      string binary_rep = "";
      for (int i = pos[0] + 1; i < number_of_digits; i++) {
        binary_rep = binary_rep + "0";
      }
      int variations = pow(2, number_of_digits - 2);
      for (int k = 0; k < 9; k++) {
        for (int j = 0; j < variations; j++) {
          for (int i = 0; i < number_of_digits - pos[0] - 1; i++) {
            if (dif[0] == dif[1] && j <= 9)
              right_part = right_part + to_string(j);
            else if (binary_rep[i] == '0')
              right_part = right_part + to_string(a);
            else
              right_part = right_part + to_string(b);
          }
          full_num = current_num + right_part;
          if (full_num >= original_num) {
            cout << full_num << "\n";
            return;
          }
          right_part = "";
          full_num = "";
          binary_rep = add(binary_rep, "1");
        }
        dif[1]++;
        a = min(dif[0], dif[1]);
        b = max(dif[0], dif[1]);
        current_num = original_num.substr(0, pos[0]);
        current_num = current_num + to_string(dif[1]);
        binary_rep = "";
        for (int i = pos[0] + 1; i < number_of_digits; i++) {
          binary_rep = binary_rep + "0";
        }
      }
    }
  }
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t;
  cin >> t;
  for (int i = 0; i < t; i++) {
    solve();
  }
  return 0;
}

### Prompt

Your challenge is to write a Cpp solution to 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 double Pi = acos(-1);
string add(string a, string b) {
  string result = "";
  int temp = 0;
  int size_a = a.size() - 1;
  int size_b = b.size() - 1;
  while (size_a >= 0 || size_b >= 0 || temp == 1) {
    temp += ((size_a >= 0) ? a[size_a] - '0' : 0);
    temp += ((size_b >= 0) ? b[size_b] - '0' : 0);
    result = char(temp % 2 + '0') + result;
    temp /= 2;
    size_a--;
    size_b--;
  }
  return result;
}
string decimalToBinary(int n) {
  string s = bitset<64>(n).to_string();
  const auto loc1 = s.find('1');
  if (loc1 != string::npos) return s.substr(loc1);
  return "0";
}
int nofdigits(int n) {
  int coun = 0;
  while (n != 0) {
    n = n / 10;
    coun++;
  }
  return coun;
}
void solve() {
  int n, k;
  cin >> n >> k;
  int num = n;
  vector<int> v;
  while (num != 0) {
    v.push_back(num % 10);
    num = num / 10;
  }
  reverse(v.begin(), v.end());
  if (k == 1) {
    int dif[2];
    memset(dif, -1, sizeof(dif));
    int number_of_digits = nofdigits(n);
    dif[0] = n / pow(10, number_of_digits - 1);
    for (int i = number_of_digits - 2; i > -1; i--) {
      int tmp = n / pow(10, i);
      if (tmp % 10 != dif[0]) {
        dif[1] = tmp % 10;
        break;
      }
    }
    if (dif[1] == -1)
      cout << n << "\n";
    else {
      if (dif[1] < dif[0]) {
        for (int i = 0; i < number_of_digits; i++) cout << dif[0];
      } else {
        for (int i = 0; i < number_of_digits; i++) cout << (dif[0] + 1);
      }
      cout << "\n";
    }
  }
  if (k == 2) {
    int dif[10];
    memset(dif, -1, sizeof(dif));
    int number_of_digits = nofdigits(n);
    dif[0] = n / pow(10, number_of_digits - 1);
    int pos[10];
    int curr = 0;
    for (int i = number_of_digits - 2; i > -1; i--) {
      int tmp = n / pow(10, i);
      if (tmp % 10 != dif[curr] && tmp % 10 != dif[0]) {
        dif[curr + 1] = tmp % 10;
        pos[curr] = number_of_digits - i - 1;
        curr++;
      }
    }
    if (dif[2] == -1)
      cout << n << "\n";
    else {
      string original_num = to_string(n);
      string current_num = original_num.substr(0, pos[0]);
      current_num = current_num + to_string(dif[1]);
      string right_part = "";
      string full_num = "";
      int a = min(dif[0], dif[1]);
      int b = max(dif[0], dif[1]);
      string binary_rep = "";
      for (int i = pos[0] + 1; i < number_of_digits; i++) {
        binary_rep = binary_rep + "0";
      }
      int variations = pow(2, number_of_digits - 2);
      for (int k = 0; k < 9; k++) {
        for (int j = 0; j < variations; j++) {
          for (int i = 0; i < number_of_digits - pos[0] - 1; i++) {
            if (dif[0] == dif[1] && j <= 9)
              right_part = right_part + to_string(j);
            else if (binary_rep[i] == '0')
              right_part = right_part + to_string(a);
            else
              right_part = right_part + to_string(b);
          }
          full_num = current_num + right_part;
          if (full_num >= original_num) {
            cout << full_num << "\n";
            return;
          }
          right_part = "";
          full_num = "";
          binary_rep = add(binary_rep, "1");
        }
        dif[1]++;
        a = min(dif[0], dif[1]);
        b = max(dif[0], dif[1]);
        current_num = original_num.substr(0, pos[0]);
        current_num = current_num + to_string(dif[1]);
        binary_rep = "";
        for (int i = pos[0] + 1; i < number_of_digits; i++) {
          binary_rep = binary_rep + "0";
        }
      }
    }
  }
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t;
  cin >> t;
  for (int i = 0; i < t; i++) {
    solve();
  }
  return 0;
}

```