K-th Lexicographical Permutation

Given a string s and an integer k, your task is to compute the k-th permutation of s in lexicographical order (1-indexed). If k exceeds the total number of unique permutations, output an empty string.

The number of unique permutations of a string with length \(n\) is at most \(n!\). Note that if the string contains duplicate characters, the total number of distinct permutations will be less.

The input consists of multiple test cases. For each test case, output the corresponding result on a separate line.

inputFormat

The first line contains an integer T denoting the number of test cases. Each of the following T lines contains a string s and an integer k separated by a space.

outputFormat

For each test case, output the k-th lexicographical permutation of the string s. If k is out of range, output an empty string. Each answer should be printed on a new line.## sample

3
abc 3
ab 4
xyz 2

bac
xzy