# 2575. Separate Connections

Partychen are analyzing a communications network with at most 18 nodes. Character in a matrix i,j (i,j both 0-based,as matrix[i][j]) denotes whether nodes i and j can communicate (‘Y’ for yes, ‘N’ for no). Assuming a node cannot communicate with two nodes at once, return the maximum number of nodes that can communicate simultaneously. If node i is communicating with node j then node j is communicating with node i.

### 输入格式

The first line of input gives the number of cases, N(1 ≤ N ≤ 100). N test cases follow.

In each test case,the first line is the number of nodes M(1 ≤ M ≤ 18),then there are a grid by M*M describled the matrix.

### 输出格式

For each test case , output the maximum number of nodes that can communicate simultaneously

### 样例

Input
2
5
NYYYY
YNNNN
YNNNN
YNNNN
YNNNN
5
NYYYY
YNNNN
YNNNY
YNNNY
YNYYN

Output
2
4
Hint
The first test case:
All communications must occur with node 0. Since node 0 can only communicate with 1 node at a time, the output value is 2.
The second test case:
In this setup, we can let node 0 communicate with node 1, and node 3 communicate with node 4.


65 人解决，178 人已尝试。

80 份提交通过，共有 710 份提交。

5.8 EMB 奖励。