Lookcook the geniosity easily finished the Canadian Computing Competition this year and got a score of ~n~. He wants to reduce his score to avoid going to CCO and having to meet AQT. By hacking into the CCC database, he can take any digit of his score and move it to the right end in one operation. However, he can only make up to ~K~ operations before he is caught. What's the minimum score he can end up with?

Input Specification

The first line contains ~T~, the number of test cases.

Then ~T~ test cases follow.

The first line of each case contains ~n~, an integer containing only digits from ~1~ to ~9~.

The second line contains ~K~, the number of digits you can move.

Output Specification

The smallest number that can be obtained by moving at most ~K~ digits of ~n~ to the end.

Constraints

~1 \le T \le 100\,000~

~2 \le n \le 10^{100\,000}~

~0 \le K \le 100\,000~

~n~ will not contain zeroes, all digits will be from ~1~ to ~9~.

The product of ~n~ across all test cases will not exceed ~10^{100\,000}~.

Sample Input

8
891
0
891
1
891
2
51111
100
98614
3
9921991111
5
1324331974
8
2364851699
5

Sample Output

891
819
189
11115
14689
1111129999
1123334479
2169934568