You have been given a String $S$ consisting of lowercase alphabets of the English Language. Now, we call a String $W$ an anagram of another String $S$, if we can obtain String $S$ be rearranging the characters of String $W$.

For example , the word $"aba"$ has $3$ anagrams i.e $["aba","aab","baa"]$ .

Now, you need to find all the disitnct anagrams of String $S$ , sort them lexicographically and then print to output the anagram that occurs at the $N^{th}$ position in this sorted order.

Can you do it ?

INPUT:

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

OUTPUT:

You need to find and print the anagram of the given 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}$