12 years back, Mr. Bean’s dad gifted him a board game. 10 years back, he lost the board along with all the toys numbered “0”. All that he had is these toys numbered from “1” to “9”. As Mr. Bean is a joker, no one was willing to play with him. So he sat on the floor and arranged these toys in ascending order i.e. “123456789”. Then he figured out the next smallest number that can be formed by rearranging the toys is “123456798”. Then he figured out the next greater number as “123456879”. Now he learnt C++ and he wants to write a program to find the next nth greater number that can be formed by rearranging the digits in the given number X. You can safely assume that such a number always exists.

Input

The first line contains a natural number t denoting the number of test cases. Then the next t lines contains the description of t test cases, each line with two natural numbers X and n.

Output

For each test case print the answer in a separate line.

Constraints

1 ≤ t ≤ 100

1 ≤ X ≤ 10¹⁸

1 ≤ n ≤ 10000

Example

Input:
3
123 1
5132 3
1112 1

Output:
132
5312
1121