Once upon a time, there was a clan named Barbarian Horde, they called it BH in short. There were 8 members in the clan: BH.BloodThirsY, BH.CrusniK, BH.ZorredekA, BH.AnsweR, BH.NobodY, BH.ShadowKnighT, BH.NomaD, BH.TyraNt.S. They used to visit the village in disguise to protect them from evils. Each night they took disguise of various heroes. Some heroes were agile, some were strong and some were wise! But they sometimes became confused to decide which hero they should choose. There were many heroes to choose from, but they had a rule, each of the chosen heroes must have names starting with a unique letter. So it was very tough for them to choose a hero by themselves, as the chosen hero may conflict with some other chosen hero by another member of the clan. So, one day, the lord of the clan chose some letters to represent the hero names. For example, if the king gave ‘dwovmqsh’, ‘d’ stands for Drow Ranger, ‘w’ for Wind Runner, ‘o’ for Omni Knight, ‘v’ for Vengeful Spirit, ‘m’ for Mirana ,‘q’ for Queen of Pain, ‘s’ for Shadow Fiend, ‘h’ for Huskar. The hero having the first letter of its name at earlier position in English alphabet are considered more powerful than the hero having first letter of its name at later position in English alphabet. All of the clan members were greedy to take the most powerful hero. To resolve this, the Queen of the clan proposed an idea. She made a chart representing all the anagrams of the word given by the lord. Then she kept the anagrams that are wavy anagrams. Wavy anagrams are the anagrams of the original word, in which, the 1st hero is more powerful than the 2nd hero, the 2nd hero is less powerful than the third hero, the third hero is more powerful than the 4th hero, the 4th hero is less powerful than the 5th hero and so on. This was done so that everyone is happy. The chosen anagrams are kept sorted lexicographically in a special box, which had many cells; each cell contained one wavy anagram of the word chosen by the BH Clan Lord. On the N-th day, the N-th cell is chosen and the N-th lexicographically smallest wavy anagram is retrieved from that cell. You are given the Lord’s chosen word W and the day number N; your job is to find the wavy anagram for that day to assign heroes to BH clan members. Input The first line of the input denotes T (≤ 1000), the number of test cases to follow. Each test case consists of a string W (0 < |W| < 24) containing only lower case letters of English alphabet with no repeated characters and a number N (fits in 64 bit signed integer). The input is such that there is always a solution. Output For each input, you have to print the case number first, followed by N-th lexicographically smallest wavy anagram of the given string W . See the sample input output for more details. Sample Input 4 take 1 take 2 take 3 take 4
2/2 Sample Output Case 1: aket Case 2: atek Case 3: ekat Case 4: etak