华东师范大学计算机科学技术系

Problem H: Separate Connections

Description

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 communicates with two nodes at once, return the maximum number of nodes that can communicates simultaneously. If node i is communicating with node j then node j is communicating with node i.

Input

The first line of input gives the number of cases,N(1<=N<=100). N test case follow. In each test case, the first line is the number of the nodes M(1<=M<=18), then there are a grid by M*M describled the matrix.

Output

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

Sample input 2 5 NYYYY YNNNN YNNNN YNNNN YNNNN 5 NYYYY YNNNN YNNNY YNNNY YNYYN

Smaple 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 node1, and node 3 communicate with node 4.

Page 9 / Total 9