Nick only likes numbers with exactly ~K~ distinct digits. Through a mysterious process that he has coined alchemy, he can convert a positive integer ~N~ to ~N+1~, though it is a tiring process.

For a given integer ~N~, compute the smallest integer greater than or equal to ~N~ with exactly ~K~ distinct digits.

Constraints

~1 \le T \le 10^5~

~1 \le K \le 10~

~1 \le N \le 10^{18}~

Input Specification

The first line contains a single positive integer, ~T~, the number of test cases. ~T~ test cases follow.

Each test case consists of a single line that contains two space-separated positive integers, ~N~ and ~K~.

Output Specification

Output the answers for the ~T~ test cases in order. There should be no blank lines in your output.

The answer for the ~i~th test case should be on the ~i~th line. Output the smallest integer greater than or equal to ~N~ with exactly ~K~ distinct digits.

Sample Input

6
1 1
1 2
1 3
11 1
11 2
11 3

Sample Output

1
10
102
11
12
102