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 program to find the minimum integer x such that x ≥ n and the number x is k-beautiful.
 def nearest_k_number(a, k):
  c = 0
  ta = a
  while ta != 0:
    ta = ta // 10
    c += 1

  numbers = set()

  counter = 0
  while c != 0:
    c = c - 1
    if c != 0:
      cur = a // (10 ** c)
    else:
      cur = a
    cur = cur % 10

    if cur not in numbers:
      counter += 1
      if counter > k:
        return a // (10 ** (c + 1)), a //(10 ** c)
      numbers.add(cur)
  return a, a

t = int(input())

def check(n, k):
  c = 0
  s = set()
  while n != 0:
    t = n % 10
    n = n // 10
    if t not in s:
      c += 1
      s.add(t)
    if c > k:
      return True
  return False

def pad(a, k):
  t = a
  m = a % 10
  c = 0
  while t != 0:
    if t % 10 < m:
      m = t % 10
    t //= 10
    c += 1
  while c < k:
    c += 1
    a = a * 10 + m
  return a

def nex(n,k,a0):
  a1 = a0
  nums = set()
  while a0 != 0:
    if a0 % 10 not in nums:
      nums.add(a0 % 10)
    a0 = a0 // 10

  if len(nums) < k:
    while a1 < n:
      a1 *= 10
    return a1 

  k = 0
  while n !=0:
    k += 1
    n = n // 10

  return pad(a1, k)

def solve(n, k):
  if k == 1:
    tn = n
    m = -1
    for n in range(1, 10):
      while n < tn:
        n = n * 10 +n % 10
      if m == -1 or m > n:
        m = n
    return m

    return n
  a = nearest_k_number(n, k)
  a0 = a[0]
  a1 = a[1]
  if a0 == n:
    return a0

  at = a0
  pr = False
  while at !=0:
    if at % 10 > a1 % 10:
      pr = True
      break
    at = at // 10

  if pr:
    a0 = a1  
  a0 += 1
  while check(a0, k):
    a0 += 1

  a0 = nex(n , k, a0)

  return a0

tn = []
tk = []
while t > 0:
  t = t - 1
  n, k = list(map(int, input().strip().split()))
  tn.append(n)
  tk.append(k)
for i in range(len(tk)):
  print(solve(tn[i], tk[i]))