You are given a string array representing Known people. Known[i][j] = 'Y' if i knows j.

Friends: A is a friend of B if B knows A or B has a friend who knows A.

True friends: A and B are true friends if A is a friend of B and B is a friend of A.

Group: Everyone in a Group must be true friends to each other.

Your task is to find the number of Groups from the given list of Known people. It can be proved that there is exactly only one possible way for forming the groups.

Input

The first line consists of an integer t, the number of test cases. For each test case, you are given an array of strings representing Known people. Known is of size N×N where N is the total number of people.

Output

For each test case, print the number of groups.

Constraints

1 ≤ t ≤ 1000

1 ≤ N ≤ 100

Known[i][j] is either 'Y' or 'N'

Known[i][i] = 'N' (Nobody knows themselves)

Example

Input:
3
3
NYN
NNY
YNN
7
NNYNNNN
NNNYYYN
NNNNNNN
YNNNNNN
NNNYNNN
NNNNNNN
NNNNNYN
7
NNNNYYN
NNNNNNN
NNNNNYN
NYNNNYY
NNNYNNN
NNYNNNY
NNNNYNN

Output:
1
7
3

Explanation

Case 1: All the friends are true friends to each other.

Case 2: No two true friends exist.

Case 3: There are 3 groups of true friends. {0}, {1}, {2, 3, 4, 5, 6}