D. Distance Parities
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Andrii had a connected graph with $$$n$$$ vertices. For every two different vertices $$$i$$$ and $$$j$$$ 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 $$$i, j$$$ Andrii told you $$$a_{i, j} = d_{i, j} \bmod 2$$$. Construct an example of a graph that Andrii could have had, or determine that such a graph does not exist and Andrii is lying to you.

Input

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

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

The $$$i$$$-th of the next $$$n$$$ lines contains a binary string $$$s_i$$$ of length $$$n$$$. The $$$j$$$-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 \lt j \le n$$$.

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

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 $$$m$$$ ($$$n-1 \le m \le \frac{n(n-1)}{2}$$$)  — the number of edges. In the $$$i$$$-th of the next $$$m$$$ 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).

Example
Input
3
3
011
101
110
4
0100
1000
0001
0010
5
01010
10101
01010
10101
01010
Output
YES
3
1 2
1 3
2 3
NO
YES
4
1 2
2 3
3 4
4 5
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 $$$1$$$ 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 $$$i, j$$$ is odd if and only if $$$i$$$ and $$$j$$$ have different parity.