There was a group of friends going on an adventurous trip to the Himalayas. They have made all the necessary arrangements for the trip. Due to some reason, one of their friend was not able to join the trip. So, there is a vacancy for one person on the trip. All of the other friends decided to take someone else on the trip in place of the friend who was not able to join the trip. But, as there are so many other people ready to go on the trip, they decided to play a game with them. They decided that the first person to answer the question will be taken for the trip along with them.

The game was that they would give a string S and a number N to the people. You have to arrange all the anagrams of the string in the lexicographical order and then tell the string which occurs at the $N^{th}$ position. If you want to go to the adventurous trip, be the first one to tell the answer.

Input:
The first line of the input contains the number of test cases denoted by T.
The next T lines of the input contain a string S and a number N.

Output:
Print the anagram of the string which occurs at the $N^{th}$ position when they are arranged in lexicographical order.

Constraints:

• $1 ≤ T ≤ 10^{4}$
• $1 ≤ |S| ≤ 20$
• $1 ≤ N ≤ 10^{18}$

Note: The string consists of lower case english alphabets only.