The Great Sultan Mahbub is having some serious issues with his memory. His busy days filled with great works and surrounded by even greater people have brought him to a situation where he has become quite forgetful. For example, he often forgets trivial things like the size of his suit, his weight, small grammatical issues related to gender & number, the address of his in-laws house, how to ride a cycle, deadlines, the day of the week, the name of the guy who forgot his wedding day and even the date of his own wedding (thus spending the day writing alternate solutions to ICPC problems). But when his father-in-law captured him to his in-laws house and he failed to recognize his mother-in-law it became a fiasco. And after some rather presumable events following that debacle, the detail of which does not seem really safe to mention, he decided that the matter has become pressing enough for his attention. His physician is startled by this weird problem and decides to collect statistical data to begin with. During the examination period consisting n consecutive days, the Sultan meets a single person everyday. He only recognizes the person if he has met him in the last k days (excluding today of course). You need to count the number of days (among these n days) he manages to recognize the people he meets. You can assume that before these n consecutive days he did not meet any person. Input The input begins with a number t (1 ≤ t ≤ 100), the number of test cases. Each of the following lines containsacase. Acasebeginswithn(1≤n≤500)&k(1≤k≤500). Alistofnnamesfollows. All names consist of a single uppercase letter and names are unique. They are given in the order of which Sultan meets them during the investigation. There won’t be any invalid character or space between any two names. Output For each test case produce a line of the form ‘Case X: Y ’. X is the serial number of the test case while Y is the number of people Sultan recognizes. Illustration of Third sample: Day 1: Sultan remembers nobody, meets ’M’. Does not recognize. Day 2: Remembers only ’M’ but meets ’A’. Does not recognize again. Day 3: Now remembers ’M’ & ’A’. Meets ’H’. Recognition count remains 0. Day 4: Forgets ’M’, remembers ’A’ & ’H’. Meets ’B’. Still nothing happens. Day 5: Forgets ’A’, remembers ’H’ & ’B’. Meets ’U’. No luck yet. Day 6: Forgets ’H’, remembers ’B’ & ’U’. Meets ’B’ again and recognizes this time making the recog- nition count 1. Sample Input 3 6 2 SULTAN 6 1 MAHBUB 6 2 MAHBUB
2/2 Sample Output Case 1: 0 Case 2: 0 Case 3: 1