Lookcook the geniosity easily finished the Canadian Computing Competition this year and got a score of . 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 operations before he is caught. What's the minimum score he can end up with?

#### Input Specification

The first line contains , the number of test cases.

Then test cases follow.

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

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

#### Output Specification

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

#### Constraints

will not contain zeroes, all digits will be from to .

The product of across all test cases will not exceed .

#### 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
```

## Comments