human
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 code to find the minimum integer x such that x ≥ n and the number x is k-beautiful.

from sys import stdin,stdout
def INPUT():return list(int(i) for i in stdin.readline().split())
def inp():return stdin.readline()
def out(x):return stdout.write(x)
import math
INT_MAX=10**13
from bisect import bisect_left
import sys
MOD=10**9+7
inf=MOD**2
from decimal import*
#===================================================================
# import kivy
# from kivy.app import App
# from kivy.uix.label import Label
#
# class A(App):
#     def build(self):
#         return Label(text="Hello ")
# if __name__=='__main__':
#     A().run()

def calc(n):
    A=list(int(ele) for ele in list(str(n)))
    bool=False

    for i in range(1,len(A)):
        if A[i]!=A[i-1]:
            if A[i]>A[i-1]:
                bool=True
                x=A[i-1]
            break
    if bool is True:
        return str(x+1)*len(A)
    else:
        return str(A[0])*len(A)
def special(a,b,n):
    l=len(str(n))
    X=[]
    for i in range(1<<l):
        ans=""
        for j in range(l):
            if (1<<j)&i:
                ans+=str(a)
            else:
                ans+=str(b)
        X.append(ans)
    return X
D=[]
for k in range(1,10):
    first=[]
    for i in range(10):
        for j in range(i+1,10):
            for ele in special(i,j,10**k):
                if int(ele)>=10**k:
                    first.append(int(ele))
    first.sort()
    D.append(first)






def calc2(n):
    if n==10**9 or len(set(list(str(n))))==1 or n<=100:
        return n
    l=len(str(n))
    X=D[l-2]
    ans=inf
    return(X[bisect_left(X,n)])

for _ in range(int(input())):
    n,k=map(int,input().split())
    if k==1:
        out(str(calc(n))+'\n')
    else:
        out(str(calc2(n))+'\n')