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 get_input():
    al = []
    for c in range(int(input())):
        t = input().split(" ")
        el = [t[0], int(t[1])]
        al.append(el)
    return al
def find_best(n,j, s):
    b = ":"
    m = ":"
    for k in s:
        if k < m:
            m = k
        if n[j]<k and k < b:
            b= k
    if b ==":":
        return False
    else:
        return n[:j] + b + m*(len(n)-j-1)
def solve(n,k):
    if k == 1:
        for i in range(1,len(n)):
            if n[i] > n[0]:
                return str(int(n[0])+1)*len(n)
            elif n[i] <n[0]:
                break
        return n[0] * len(n)
    s = []
    for i in range(len(n)):
        if n[i] not in s:
            if len(s) == k:
                rf = find_best(n,i,s)
                if rf != False:
                    return rf
                for j in range(i-1,-1,-1):
                    if n[j] == '9':
                        continue
                    elif n[j] in n[:j]:
                        rf = find_best(n,j,s)
                        if rf != False:
                            return rf
                    else:
                        c = str(int(n[j]) + 1)
                        cm = c
                        for k in range(j):
                            if n[k]< cm:
                                cm = n[k]
                        d = True
                        for k in range(0,j):
                            if n[k] != c:
                                d = False
                                break
                        if d:
                            return n[:j] + c + '0'*(len(n)-j-1)
                        return n[:j] + c + min(cm,c)*(len(n)-j-1)
            s.append(n[i])
    return n

    
# print(solve("209", 2))
            
def main():
    arr_list = get_input()
    for n in arr_list:
        r = solve(n[0], n[1])
        print(r)
main()