Knowledgeable Andrii#12893

Knowledgeable Andrii

1 second
256 megabytes
Hard

Andrii had a connected graph with vertices. For every two different vertices and of this graph, he calculated the length of the shortest path between them  — d_{i, j}. Unfortunately, then Andrii lost the graph and forgot the numbers d_{i, j}. But he remembered the parity of all numbers d_{i, j}.

So for every two different vertices Andrii told you a_{i, j} = d_{i, j} \bmod 2. Construct an example of a graph that Andrii could have, or determine that such a graph does not exist and Andrii is lying to you.

Input

The first line contains a single integer (1 \le t \le 10^4)  — the number of test cases. Then follows a description of the test cases.

The first line of each test case contains one integer (2 \le n \le 500)  — the number of vertices. binary lines follow.

The -th of the next lines contains a binary string s_i of length . The -th character of this string is 0 if a_{i, j} = 0, and 1 if a_{i, j} = 1.

It is guaranteed that a_{i, i} = 0 for all 1 \le i \le n, and a_{i, j} = a_{j, i} for all 1 \le i < j \le n.

It is guaranteed that the sum of n^2 over all test cases does not exceed .

Output

For each test case, if such a graph does not exist, print NO.

Otherwise, print YES. On the next line print a single integer (n-1 \le m \le \frac{n(n-1)}{2})  — the number of edges. In the -th of the next lines print two numbers u_i, v_i (1 \le u_i, v_i \le n, u_i \neq v_i), denoting the edge between the vertices u_i and v_i.

All edges must be pairwise distinct. The graph must be connected.

You can print YES and NO in any case (e.g. the strings yEs, yes, Yes will be taken as a positive answer).

Examples

Example 1

Loading
Loading

Note

In the first test case, such a graph on three vertices exists  — you can just take a triangle. All pairwise distances are equal to and hence odd.

It can be shown that in the second test case, such a graph does not exist.

In the third test case, we have a chain with edges (1, 2), (2, 3), (3, 4), (4, 5). In it, the distance between vertices is odd if and only if and have different parity.