The alphabet of a certain alien language consists of n distinct symbols. The symbols are like the letters of English alphabet but their ordering is different. You want to know the original order of the symbols in that particular alphabet. You have a string consists of all the letters of that alphabet and you know that this is the k-th (1 based) lexicographic permutation of these symbols. You have to arrange these symbols in lexicographic order of that language. Input The first line of input will contain an integer T (T ≤ 5000) which denotes the number of test cases. Each of the following T lines contains a string s and an integer k. The string will be of length n (1 ≤ n ≤ 20) and will consist of lowercase letters only. All the letters in the string will be distinct. The value of k will be in the range (1 ≤ k ≤ n!). Output For each line of input output the case number and a string which contains the letters in lexicographic order in that language. Note: The first input resembles the original order of English alphabet. Here are the lexicographic permutations abcd 1 abdc 2 acbd 3 acdb 4 adbc 5 adcb 6 bacd 7 badc 8 bcad 9 bcda 10 bdac 11 bdca 12 cabd 13 cadb 14 cbad 15 cbda 16 cdab 17 cdba 18 dabc 19 dacb 20 dbac 21 dbca 22 dcab 23 dcba 24 Sample Input 3 bdac 11 abcd 5 hjbrl 120 Sample Output Case 1: abcd Case 2: acdb Case 3: lrbjh