Today is 21st December. After 2 days, the Intra AUST Programming Contest will take place.Shibli is in charge of the problem set of the contest.Some of the students want to know the problems of Intra AUST in advance.So they planned to hack Shibli's Toph account. They got to manage his password which is a string of length n and consists of only lowercase English letters (a - z).
Unfortunately, Shibli came to know about their plan. So he changed his password.But they didn't lose hope. They know Shibli likes Palindromes and he doesn't like vowels.His new password is a longest palindromic substring of the previous password that can have at most K numbers of vowels. A palindrome is a word, phrase, number, or other sequence of characters which reads the same backward as forward.
You are one of the best hackers in BD.They give you the previous password.You have to find the new password.If there are more than one possible password, find the lexicographically smallest one. If you can't find the new password, report "not found" .
See the sample I/O for better understanding.
Input
The first line of the input is an integer T(1<=T<= 50) ,denoting the number of test cases.Each test case has two lines. The first line contains two integers n(1<=n<=100000) and k(0<=k<=n) .The next line contains a string of length n.
Output
There will be T lines of output in the form of "Case X: Y". where X is the case number and Y is a string which is either the new password or "not found".
Sample
| Input | Output |
|---|---|
3 5 1 abcba 6 5 aaaaaa 3 0 aei | Case 1: bcb Case 2: aaaaa Case 3: not found |
