human
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
impor ... Can you provide a Python code to find the minimum integer x such that x ≥ n and the number x is k-beautiful?
assistant
#Here is Python code to find the minimum integer x such that x ≥ n and the number x is k-beautiful.
t sys

def get_digits(n):
    digits = []
    while n != 0:
        digits.append(n % 10)
        n = n // 10

    return digits[::-1]

def construct(digits):
    result = 0
    power = 1
    for d in digits[::-1]:
        result += power * d
        power *= 10
    return result

def solve(n, k):

    digits = get_digits(n)
    # print(n, k)
    # print(digits)

    if len(set(digits)) <= k:
        return n

    met = [False for _ in range(10)]
    counter = 0
    for i, d in enumerate(digits):
        if met[d] == True:
            continue

        if counter == k:
            break

        met[d] = True
        counter += 1

    # print(met)
    for t in range(digits[i] + 1, 10):
        if met[t] == True:
            answer = (digits[:i] + [t] +
                      [min(digits[:i])] * (len(digits) - i - 1))
            return construct(answer)

    prefix = construct(digits[:i])
    # print(prefix)
    sub_answer = get_digits(solve(prefix + 1, k))
    sub_k = len(set(sub_answer))
    if sub_k < k:
        filler = 0
    else:
        filler = min(sub_answer)
    answer = sub_answer + [filler] * (len(digits) - len(sub_answer))
    return construct(answer)

# def test():
#     n = 200
#     for k in range(1, 7):
#         k = 2
#         for i in range(1, n + 1):
#             x = solve(i, k)
#             print(i, k, x)
#             if len(set(get_digits(x))) > k or (x < i):
#                 print('Ooops')
#                 print(i, k, x)
#                 break
#         break

def main():
    outputs = []
    fin = sys.stdin
    # fin = open('input.txt')
    N = int(fin.readline())
    for _ in range(N):
        n, k = map(int, fin.readline().split())
        outputs.append(solve(n, k))

    print('\n'.join(map(str, outputs)))

if __name__ == '__main__':
    main()
    # test()