Lexicographically Smallest String After K Swaps

You are given a string S consisting of lowercase English letters and an integer K. You are allowed to perform exactly K swaps on the string. In each swap, you can choose two positions in the string and swap the characters.

Your task is to compute the lexicographically smallest string that can be obtained by performing at most K swaps following the strategy described below:

Let \( S = s_1 s_2 \ldots s_n \) and let the sorted order of the characters be \( sorted(S) = t_1 t_2 \ldots t_n \). Then, for each position \( i \) from 1 to \( n \), if \( s_i \neq t_i \), search for an index \( j \) (with \( j > i \)) such that \( s_j = t_i \) and swap \( s_i \) and \( s_j \). Count the swap and stop if you have already performed exactly K swaps. If fewer than K swaps are possible, output the string as is.

Note: If the string is already the lexicographically smallest, no swaps are performed even if K > 0.

inputFormat

The first line contains an integer T representing the number of test cases. Each of the next T lines contains a test case with a string S (consisting of lowercase letters only) and an integer K separated by a space.

outputFormat

For each test case, output the lexicographically smallest string after performing at most K swaps. Each output should be printed on a new line.

## sample

5
ab 1
bbba 2
ba 1
ab 0
bba 3

ab
abbb
ab
ab
abb

</p>