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
impor ... What is a Python program to find the minimum integer x such that x ≥ n and the number x is k-beautiful?
assistant
#Here is Python program to find the minimum integer x such that x ≥ n and the number x is k-beautiful.
t os, sys, math
from io import BytesIO, IOBase
ip = lambda: input()
it = lambda: int(input())
ma = lambda: map(int, input().split(" "))
li = lambda: list(map(int,input().split(" ")))
mod=10**9+7

def m1(n,l):
    return n*l

def solve(a,b,s,l):
    x=a
    t=1
    g,h=min(a,b),max(a,b)
    for i in range(1,l):
        if x+g+h*(l-t-1)>=s:
            x+=g
            t+=1
        else:
            x+=h
            t+=1
    return x

def main():
    for _ in range(int(input())):
        n,k=ma()
        s=str(n)
        l=len(s)
        ans=m1(s[0],l)
        if ans<s:
            ans=m1(str(int(s[0])+1),l)
        if k==1:
            print(ans)
            continue

        if s==s[0]*l:
            print(s)
            continue

        i=1
        while s[i]==s[0]:
            i+=1

        z=solve(s[0],s[i],s,l)
        if z>=s and ans>z:
            ans=z
        if ord(s[0])-ord(s[i]) ==1:
            g='0'
        else:
            g=str(int(s[i])+1)
        z=solve(s[0],g,s,l)
        if z>=s and ans>z:
            ans=z
        print(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)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
      ...