Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
F2. Nearest Beautiful Number (hard version)

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputIt is a complicated version of problem F1. The difference between them is the constraints (F1: $$$k \le 2$$$, F2: $$$k \le 10$$$).

You are given an integer $$$n$$$. Find the minimum integer $$$x$$$ such that $$$x \ge 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 \le t \le 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 \le n \le 10^9$$$, $$$1 \le k \le 10$$$).

Output

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

Example

Input

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

Output

2021 181111 34533 724542 999999999 12345678

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/20/2021 07:58:09 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|