Given a string S, generate all different possible set of K characters in the string with P paddings, and sort them in lexicographic (dictionary) order. A padding is expressed as an underline '_'. For example, if K=2 and P=1, and the given string S is ‘CDBABBD’, the output would be
_AB
_AC
_AD
_BB
_BC
_BD
_CD
_DD
A_B
A_C
A_D
B_B
B_C
B_D
C_D
D_D
AB_
AC_
AD_
BB_
BC_
BD_
CD_
DD_
The first line of input contains a positive integer T (T <= 30), which indicates the number of test cases.
For each case, there is a string S (length| <= 100), a positive integer K (K <= 10), and a nonnegative integer P (P <= 3) in a line. The length of S is less than or equal to 100 and S contains only 'A'-'J'; The number K, less than or equal to 10, indicates the number of non-padding characters in an output set. The nonnegative integer P indicates the number of paddings.
For each test case, print in each line all different possible sets of K characters in the string with P paddings. The answers have to be sorted in the dictionary order, one substring per line.