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.
4 bcda 20 cbad 5 ydvtrs 268 asfda 32
dacb adbc srdvyt dfasa
For case 2, one need to find the anagram of "cbad" which occurs at 5th place when arranged in lexicographical order. The anagrams that occur at first four positions are abcd, abdc, acbd and acdb respectively. The fifth anagram is adbc.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor