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 check(s, k, t, n):
    # Check if the number s, but with last digit t, is k-beautiful.
    z = set()
    for i in range(len(s)):
        if(i == len(s)-1):
            z.add(t)
        else:
            z.add(int(s[i]))
    if(len(z)<=k):
        # Print the number
        needed = len(str(n)) - len(s)
        arr = []
        min_val = 9
        for i in range(len(s)):
            if(i == len(s)-1):
                arr.append(t)
                if(t < min_val):
                    min_val = t
            else:
                arr.append(int(s[i]))
                if(int(s[i])<min_val):
                    min_val = int(s[i])
        if(len(z)==k):
            for i in range(needed):
                arr.append(min_val)
        else:
            for i in range(needed):
                arr.append(0)
        for i in range(len(arr)):
            print(arr[i], end='')
        print()
        return True
    return False

def func(n, i, k):
    # Check for the number from 0 to i.
    s = str(n)[0:i+1]
    t = int(s[-1]) + 1
    # Check k-beauty of s for [t ---> 9]
    while(t < 10):
        if(check(s, k, t, n)):
            # print(s, k, t)

            return 0
        else:
            t += 1
    func(n, i-1, k)

for _ in range(int(input())):
    n, k = map(int, input().split())
    l = len(str(n))
    if(check(str(n), k, int(str(n)[-1]), n)):
        continue
    func(n, l-1, k)