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}$$