Department of CSE students of the Ahsanullah University of Science and Technology loves to tour whenever they get a break from their hectic regular and makeup class schedule. Whenever a couple of friends go for a tour they love to sing songs. Unfortunately, not all the friends know the lyrics to the same song.. If there is M possible Songs and N friends are going for a tour can you please find what is the minimum number of songs need to be performed so that all students can part of any of one song. Everybody knows at least one for sure. It is guaranteed that you can always select the minimum number of songs.
Input
The first line contains an integer T ( 1 <= T <= 50 ) i.e. the number of Test cases. T test cases follow. There is a integer N ( 1 <= N <= 100 ) number of students going for a tour in first line of every test case . Then N lines follow . Each of the N lines contain a M ( 1 <= M <= 15 ) characters string and M is same for each of the N lines. The **jth **character of the ith element of string is 'Y' if the ith student knows the jth song, and 'N' if he doesn't.
Output
For each test case, print a line “Case x: y” where x is replaced by the test case number and y is minimum number of songs need to be selected so that all students can perform at least one song.
Sample
| Input | Output |
|---|---|
3 3 YN NY NY 4 NNYYY YYYNY NNNYN YNNNN 3 NY YY NY | Case 1: 2 Case 2: 2 Case 3: 1 |
