human
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
The above is tricky. Write me a correct solution in PYTHON3.
 Give me a Python code to find the minimum integer x such that x ≥ n and the number x is k-beautiful?
assistant
#Here is Python code to find the minimum integer x such that x ≥ n and the number x is k-beautiful.

# by the authority of GOD     author: manhar singh sachdev #

import os,sys
from io import BytesIO, IOBase
from collections import Counter

def comp(arr1,arr2):
    # arr1 = ans
    if len(arr1) > len(arr2):
        return 1
    if len(arr1) < len(arr2):
        return 0
    for i,j in zip(arr1,arr2):
        if i > j:
            return 1
        if i < j:
            return 0

def main():
    for _ in range(int(input())):
        n,k = input().split()
        k = int(k)
        n = list(map(int,n))
        if len(Counter(n)) <= k:
            print(''.join(map(str,n)))
            continue
        le = len(n)
        ans = [1]+[0]*le if k >= 2 else [1]*(le+1)
        curr = []
        mini = float("inf")
        uni = Counter()
        for idx,i in enumerate(n):
            if len(uni) > k:
                break
            for j in range(i+1,10):
                uni[j] += 1
                if len(uni) < k:
                    poss = curr + [j] + [0]*(le-idx-1)
                    if comp(ans,poss):
                        ans = poss
                elif len(uni) == k:
                    mini1 = min(mini,j)
                    poss = curr + [j] + [mini1]*(le-idx-1)
                    if comp(ans,poss):
                        ans = poss
                uni[j] -= 1
                if not uni[j]:
                    del uni[j]
            mini = min(mini,i)
            curr += [i]
            uni[i] += 1
        print(''.join(map(str,ans)))

# Fast IO Region
BUFSIZE = 8192
class FastIO(IOBase):
    newlines = 0
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
  ...