All Submissions


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

Submit

Login to post clarification.

No Clarifications.

Contest

Mode Judge

Passive

Online

Overall Rankings

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