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 solve(num, k):
    count = 0
    tab = [-1 for _ in range(int(k))]
    idx = 0
    rem = -1
    rem_idx = -1
    for x in num:
        if int(x) not in tab:
            if count < int(k):
                tab[count] = int(x)
                count += 1
            else:
                rem = int(x)
                rem_idx = idx
                break
        idx += 1

    if rem == -1:
        print(num)
        return

    idx_1 = 0
    # idx_2 = 0
    # sec_tab = []
    # for x in range(rem_idx, -1, -1):
    #     if int(num[x]) < max(tab):
    #         idx_1 = x
    #         break
    # for x in range(rem_idx+1):

    check = False
    counter = 0
    sec_tab = []
    new = min(tab)
    if max(rem, max(tab)) == rem:
        for x in range(rem_idx, -1, -1):
            if int(num[x]) < max(tab):
                idx_1 = x
                break

        for x in range(rem_idx + 1):
            if int(num[x]) not in sec_tab:
                if counter == count-1:
                    idx_2 = x
                    break
                else:
                    counter += 1
                    sec_tab.append(int(num[x]))

        if idx_2 >= idx_1:
            counter = 0
            for x in num:
                if int(x) not in sec_tab and not check:
                    print(int(x)+1, end = "")
                    check = True
                    if int(x)+1 not in sec_tab:
                        sec_tab.append(int(x)+1)

                    if len(sec_tab) == count:
                        new = min(sec_tab)
                    else:
                        new = 0

                        # if int(x) == min(tab):
                        # if int(x) == min(tab) and int(x)+1 in tab:
                        #     new = 0
                        # elif int(x)+1 not in tab:
                        #     if int(x) == min(tab):
                        #         new = int(x)+1
                        #         # for i in range(len(tab)):
                        #         #     if tab[i] == int(x):
             ...