# Practice on Toph

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

# Tour

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 **j ^{th }**character of the

**ith**element of string is ‘

**Y**’ if the

**ith**student knows the

**j**song, and ‘

^{th}**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

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 |