human
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":


 ... 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.
 def f(n,k):
    dig_set = set()
    pre = ''
    for x in n:
        dig_set.add(x)
        if len(dig_set)>int(k): 
            post_head = x
            dig_set.remove(x)
            break
        pre += x
        post_head=""

    post = n[len(pre):] 

    if post_head:
        min_dig = min(dig_set)
        poss_digs = {i for i in dig_set if i>x}
        if poss_digs:
            min_poss_dig = min(poss_digs)
            ans = pre+min_poss_dig+min_dig*(len(post)-1)
        else:
            pre = str(int(pre)+1)
            if len(set(pre))==int(k):
                ans = pre+min(set(pre))*(len(post))
            elif len(set(pre))<int(k):
                ans = pre+"0"*(len(post))
            else:
                ans = f(pre+"0"*(len(post)),k)
    else:
        ans = pre
    
    return ans

for i in range(int(input())):
    n,k = input().split()
    print(f(n,k))