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.
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 .
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).
Example 1
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.