You are given an integer N.
Now you have to perform the following operation exactly K times :-
Choose two different positions, i and j, and swap the digits at those positions. This swap must not cause the resulting number to have a leading zero.

You have to find the maximal possible number one can get at the end of this procedure. If it's not possible to perform K operations, print -1 instead.

Input

The first line will contain the no. of test cases T.
For each test case there will be two integers N and K separated by a space.

Output

For each test case output a single integer (i.e. maximal possible number formed) in a separate line.

Constraints

1<=N<=1,000,000
1<=K<=10
1<=T<=300

Sample Input

``` 5 21395 1 765 1 70 5 8 2 215649 2 ```

Sample Output

``` 91325 756 -1 -1 965142 ```

Problem Setter:- Nitish Agarwal

Languages: C,C++,C#,Java,JavaScript,Pascal,Perl,PHP,Python,Ruby

Time Limit: 1 Second(s)
Score: 100 Point(s)
Input File Limit: 50000 Bytes

Mode Judge

RankNameScore
1xyz0
2Ams0
3TIP0
4team420
5xyzz0
6asdasdasd0
7abcd0
8khankhan0
9Gabriel0
10gigel0