New sorting machine has been discovered. This machine takes both words and numbers alternatively. Words can also be upper and lower case. This machine has to convert the Upper case letters to lower case and sort them.

Yous task is to study the sorting machine. This machine works on Selection sort algorithm. Your given a iteration number at which the result has to be printed. In first iteration you have to iterate the words using selection sort and next number and it follows till it reaches the mentioned iteration number.

INPUT: First line contains T denotes the no of test cases. Each test case has a string comprises of words and numbers alternatively and in next line contains a iteration number. OUTPUT: Output the sorting machine output at mentioned iteration number.