human
PYTHON3 solution for "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":
assistant
#Here is Python code to find the minimum integer x such that x ≥ n and the number x is k-beautiful.
 def F1(s, k):
  siz = len(s)
  pivot = s[0]
  index = 1
  while index < siz:
    if s[index] != pivot: break
    else: index += 1
  if index == siz: return s
  elif pivot > s[index]:
    res = s[:index]
    for i in range(index, siz):
      res += pivot
    return res
  else:
    res = ""
    ch = str(int(pivot) + 1)
    for i in range(siz):
      res += ch
    return res

def replaceF(res, f, start, siz):
  for i in range(start, siz):
    res += f
  return res

def F2(s, k):
  siz = len(s)
  f1 = s[0]
  index = 1
  while index < siz:
    if s[index] != f1: break
    else: index += 1
  if index == siz: return s
  f2 = s[index]
  pos = index + 1
  while pos < siz:
    if s[pos] != f1 and s[pos] != f2: break
    else: pos += 1
  if pos == siz: return s
  minF = min(f1, f2)
  maxF = max(f1, f2)

  if s[pos] < minF: 
    res = s[:pos]
    return replaceF(res, minF, pos, siz)

  elif s[pos] < maxF:
    res = s[:pos]
    res += maxF
    return replaceF(res, minF, pos + 1, siz)

  elif s[pos - 1] == minF:
    res = s[:(pos-1)]
    maxInt = int(maxF)
    minInt = int(minF)

    if minF not in res:
      res += str(minInt + 1)
      if maxInt > minInt + 1: minF = str(minInt + 1)
      else: minF = str(0)
    else:
      res += maxF
      
    return replaceF(res, minF, pos, siz)

  else:
    stand = pos - 1
    while stand >= 0:
      if s[stand] == minF: break
      else: stand -= 1
    option = False
    for i in range(stand, -1, -1):
      if s[i] == maxF:
        option = True
        break

    if option:
      res = s[:stand]
      maxInt = int(maxF)
      minInt = int(minF)
      # res += maxF
      # if minF not in res:
      #   minF = str(0)

      if minF not in res:
        res += str(minInt + 1)
        if maxInt > minInt + 1: minF = str(minInt + 1)
        else: minF = str(0)
      else:
        res += maxF

      return replaceF(res, minF, stand+1, siz)
    else:
      res = s[:stand + 1]
      res += str(int(maxF) + 1)
      return replaceF(res, minF, stand + 2, siz)

case = int(input())
for t in...