human
Write me a Python program to find the minimum integer x such that x ≥ n and the number x is k-beautiful given the following:
PYTHON3 solution for "It is a complicated version of problem F1. 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 ≤ 10).

Output

For each test case output on a separate line x — the minimum k-beautiful integer such that x ≥ n.

Example

Input

6
2021 3
177890 2
34512 3
724533 4
998244353 1
12345678 10

Output

2021
181111
34533
724542
999999999
12345678":
assistant
#Here is Python program to find the minimum integer x such that x ≥ n and the number x is k-beautiful.
 def naiveSolve(n,k):
    
    i=n
    while True:
        i2=i
        u=set()
        while i2>0:
            u.add(i2%10)
            i2//=10
        if len(u)<=k:
            return i
        i+=1
    
    return

def solve(n,k):
    narr=[]
    n2=n
    while n2>0:
        narr.append(n2%10)
        n2//=10
    narr.reverse()
    
    ansarr=[]
    unique=set()
    stoppingIndex=-1
    for i,x in enumerate(narr):
        if x in unique or len(unique)+1<=k:
            ansarr.append(x)
            unique.add(x)
        else:
            stoppingIndex=i
            break
    # print(unique,stoppingIndex,ansarr)
    if stoppingIndex!=-1: # stopped
        seen=sorted(unique)
        if narr[stoppingIndex]<max(seen): # put a larger seen number
            for x in seen:
                if x>narr[stoppingIndex]:
                    ansarr.append(x)
                    break
            while len(ansarr)<len(narr): # put smallest seen number
                ansarr.append(min(seen))
        else:
            # narr[stoppingIndex]>max(seen). must increase some prev. number
            i=stoppingIndex-1
            while True:
                ansarr[i]+=1
                if ansarr[i]==10: # cannot
                    ansarr.pop()
                    i-=1
                    continue
                if len(set(ansarr))<=k: # ok
                    break
            
            unique=set(ansarr)
            if len(unique)==k-1: # place 0s
                remaining=0
            else: # place minimum previous
                remaining=min(unique)
            while len(ansarr)<len(narr):
                ansarr.append(remaining)
    ans=0
    for x in ansarr:
        ans*=10
        ans+=x
    return ans

def main():
    
    t=int(input())
    allans=[]
    for _ in range(t):
        n,k=readIntArr()
        ans=solve(n,k)
        allans.append(ans)
    multiLineArrayPrint(allans)
    
    # for n in range(4000,5000):
    #     for k in range(1,11):
    #         ans=solve(n,k)
    #         ans2=naiveSolve(n,k)
   ...