Problem Of The Week (4/10/2009)

Popular Friend

Problem Statement

You want to find the most popular person in a social network (orkut, for example). To do this, you will count the number of "M-friends" that each person has. Person A is called an M-friend of another person B if they are friends with each other or if there exists some person C who is a friend of both A and B. The most popular person is the person with the highest number of M-friends. (There might be more than one if multiple people all have the maximal number of M-friends).

Input

The first line in input will contain an integer T. T test cases follow. In each test case first line consists of an integer S, denoting the size of the social network. Then S lines follow, each containing S characters (making a complete SxS matrix, call it friends[][]). Each character is either 'N' or 'Y'.

If the ith character of the jth line is 'Y' this means i and j are friends (hence jth character of ith line will also be 'Y').

Output

Output a single integer P for each case representing the number of M-friends of the most popular person in this social network.




Constraints

• 1<=S<=50

Sample

Input

5
3
NNN
NNN
NNN
3
NYY
YNY
YYN
5
NYNNN
YNYNN
NYNYN
NNYNY
NNNYN
10
NNNNYNNNNN
NNNNYNYYNN
NNNYYYNNNN
NNYNNNNNNN
YYYNNNNNNY
NNYNNNNNYN
NYNNNNNYNN
NYNNNNYNNN
NNNNNYNNNN
NNNNYNNNNN
15
NNNNNNNNNNNNNNY
NNNNNNNNNNNNNNN
NNNNNNNYNNNNNNN
NNNNNNNYNNNNNNY
NNNNNNNNNNNNNNY
NNNNNNNNYNNNNNN
NNNNNNNNNNNNNNN
NNYYNNNNNNNNNNN
NNNNNYNNNNNYNNN
NNNNNNNNNNNNNNY
NNNNNNNNNNNNNNN
NNNNNNNNYNNNNNN
NNNNNNNNNNNNNNN
NNNNNNNNNNNNNNN
YNNYYNNNNYNNNNN

Output
 

0
2
4
8
6

Explanations:

1. Here, there are 3 people and none of them are friends, so everybody has zero M-friends.
2. Each person has two M-friends.
3. Persons 0 and 4 have two M-friends, persons 1 and 3 have three M-friends. Person 2 is the most popular one - four M-friends.