#1594 AddElectricalWires

35  1 s   128 MB  

Description

You are given an electrical circuit for a home, with a number of nodes possibly connected by wires. Any pair of nodes may be connected by at most one wire, and a node can't be connected to itself. Each node on the circuit is either an electrical outlet for the house or a connection to the main electrical grid. The matrix of characters W tells you the wires that are already in place; the xth character of the yth row is '1' (one) if nodes x and y have a wire between them, '0' (zero) otherwise. The list of integers lists the indices of the nodes that are connections to the main electrical grid. 
You'd like to make the circuit safer and more redundant by adding as many extra wires to it as possible. The one complication is that no two main grid connections are currently wired together (directly or indirectly), and you must preserve this, or else disaster will result. Determine the maximum number of new wires you can add to the circuit.

Input

The first line of the input gives a number of test cases, T.
The first line of each case gives the number of nodes N (1 <= N <= 50), the number of elements in G.
The next line contains each elements of G.
Next N line contains each element of W.

Output

For each test case, output the maximum number of new wires on each line.

Sample Input

Sample Output

3
3 1
0
000
000
000
3 2
0 1
000
000
000
2 1
0
01
10
3
1
0