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

def naiveSolve():
    

    
    return

def solve(n,k):
    narr=[]
    n2=n
    while n2>0:
        narr.append(n2%10)
        n2//=10
    narr.reverse()
    
    ansarr=narr.copy()
    while len(set(ansarr))>k:
        ansarr[-1]+=1
        while ansarr[-1]==10:
            ansarr.pop()
            ansarr[-1]+=1
    if len(set(ansarr))<k:
        append=0
    else:
        append=min(ansarr)
    while len(ansarr)<len(narr):
        ansarr.append(append)
        
        
    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)
    
    return

import sys
input=sys.stdin.buffer.readline #FOR READING PURE INTEGER INPUTS (space separation ok)
# input=lambda: sys.stdin.readline().rstrip("\r\n") #FOR READING STRING/TEXT INPUTS.

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))
def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))
def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))
 
def readIntArr():
    return [int(x) for x in input().split()]
# def readFloatArr():
#     return [float(x) for x in input().split()]
 
def makeArr(defaultValFactory,dimensionArr): # eg. makeArr(lambda:0,[n,m])
    dv=defaultValFactory;da=dimensionArr
    if len(da)==1:return [dv() for _ in range(da[0])]
    else:return [makeArr(dv,da[1:]) for _ in range(da[0])]
 
def queryInteractive(x):
    print('{}'.format(x))
    sys.stdout.flush()
    return int(input())
 
def answerInteractive(ans):
    print('! {}'.format(ans))
    sys.stdout.flush()
 
inf=float('inf')
# MOD=10**9+7
MOD=998244353

from math import gcd,floor,ceil
# from math import floor,ceil # for Python2
 
for _abc in range(1):
    main()