Amy is a lexicographer. As you know, a lexicographer makes and edits dictionaries. She loves dictionaries so much, that she wanted to find all possible words formed by permuting the string. However it is taking a lot of time and she wants you to help her by finding some of the permutations for her. You will be given T strings, of max length N, and you have to find out the lexicographically K th string formed by using all the letters of the string.

Input: The first line contains T denoting the number of strings. The next T lines will contain a string with each character in lowercase and K each.

Output: For each of the test cases output a string in a new line.

Constraints:

1 <= T <= 10^5

1 <= N <= 20

1 <= K < Number of possible permutations of the string

Example:

Input

2

string 1

string 2

Output

ginrst

ginrts

Problem Setter - Rohan