human
Write me a Python code to find the minimum integer x such that x ≥ n and the number x is k-beautiful given the following:
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
Solve the task in PYTHON3.
assistant
#Here is Python code to find the minimum integer x such that x ≥ n and the number x is k-beautiful.

def one(n: str, lili: dict):
  
  sel = n[0]
  def have_greater_in_lili_or_sel(digit: str) -> bool:
    for li, exists in lili.items():
      if exists and li > digit:
        return True
    return sel > digit
  
  for digit in n[1:]:
    # if the digit is less than sel or we already have a greater digit.
    if have_greater_in_lili_or_sel(digit):
      # we have a safe tight choice.
      break
    # if we already have that digit, continue.
    if digit in [d for d in lili if lili[d]]:
      continue
    # if the digit is greater than sel and we don't have the digit or a greater one.
    if digit > sel:
      sel = str(int(sel) + 1)
      # if we already has dat digit(sel+1), we still got a spare k.
      if lili[sel]:
        # Set the lowest value to true then.
        lili['0'] = True
      break
  lili[sel] = True

def run(n: str, k: int, lili: dict):
  if not n or not k:
    return
  elif lili[n[0]]:
    run(n[1:], k, lili)
  elif k == 1:
    one(n, lili)
  else:
    lili[n[0]] = True
    run(n[1:], k - 1, lili)

def clean(n: str, lili: dict) -> str:
  
  def least_greater(n_dig: str, res_dig: str) -> str:
    best = res_dig
    for digit, exists in lili.items():
      if exists and digit > n_dig:
        best = min(best, digit)
    return best
  
  maybe_a_better_resut = ''
  min_dig = min(digit for digit in '0123456789' if lili[digit])
  max_dig = max(digit for digit in '0123456789' if lili[digit])
  for curr_index, n_dig in enumerate(n):
    best = least_greater(str(int(n_dig) - 1) , max_dig)
    if best > n_dig:
      # If the best is bigger than the number itself,
      # add it and fill the rest with the min_val we have.
      maybe_a_better_resut += best
      for _ in range(len(n) - curr_index - 1):
        maybe_a_better_resut += min_dig
      break
    elif best < n_dig:
      parent = maybe_a_better_resut[curr_index - 1]
      # If the best was smaller than the number itslef,
      # then we have to set our parent to a greater value
      # and fill the rest with min_val.
     ...