Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Tour

Limits 1s, 512 MB

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.

Samples

InputOutput
3
3
YN
NY
NY
4
NNYYY
YYYNY 
NNNYN
YNNNN
3
NY
YY
NY
Case 1: 2
Case 2: 2
Case 3: 1

Discussion
Submit

Login to submit