human
Can you provide a Python program to find the minimum integer x such that x ≥ n and the number x is k-beautiful given the following:
Can you solve the below in PYTHON3?
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.

import sys
input = lambda: sys.stdin.readline().strip()

# sys.stdin = open('input.txt', 'r')
# sys.stdout = open('output.txt', 'w')

def solve():
    n, k = map(int, input().split())
    s = str(n)
    if len(set(s))<=k:
        return n
    L = len(s)
    def helper(a,b):
        i = 0
        while i<len(s) and s[i] in a+b:
            i += 1
        if s[i]>b:
            j = i-1
            while j>=0 and s[j]==b:
                j -= 1
            if j>=0:
                return s[:j] + b + a*(L-j-1)
            else:
                return '9'*L
        elif s[i]<a:
            return s[:i] + a*(L-i)
        else:
            return s[:i] + b + a*(L-i-1)
    if k==1:
        i = 0
        while s[i]==s[0]:
            i += 1
        if s[i] < s[0]:
            res = s[0] * L
        else:
            c = str(int(s[0]) + 1)
            res = c * L
    else:
        res = min(helper(str(a),str(b))
                for a in range(10) for b in range(a+1,10))
    return res

for _ in range(int(input())):
    print(solve())