Andrii 曾拥有一个包含 $n$ 个顶点的连通图。对于图中任意两个不同的顶点 $i$ 和 $j$，他计算了它们之间的最短路径长度 $d_{i,j}$。不幸的是，Andrii 后来丢失了这个图，并忘记了所有的 $d_{i,j}$。但他记住了所有 $d_{i,j}$ 的奇偶性。

因此，对于每两个不同的顶点 $i, j$，Andrii 告诉你 $a_{i,j} = d_{i,j} \pmod 2$。请构造一个 Andrii 可能拥有的图，或者确定这样的图不存在，即 Andrii 在撒谎。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 10^4$)，表示测试用例的数量。接下来是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ ($2 \le n \le 500$)，表示顶点数量。

接下来的 $n$ 行中，第 $i$ 行包含一个长度为 $n$ 的二进制字符串 $s_i$。该字符串的第 $j$ 个字符在 $a_{i,j} = 0$ 时为 0，在 $a_{i,j} = 1$ 时为 1。

保证对于所有 $1 \le i \le n$，$a_{i,i} = 0$，且对于所有 $1 \le i < j \le n$，$a_{i,j} = a_{j,i}$。

保证所有测试用例的 $n^2$ 之和不超过 250000。

输出格式

对于每个测试用例，如果这样的图不存在，输出 NO。

否则，输出 YES。在下一行输出一个整数 $m$ ($n - 1 \le m \le \frac{n(n-1)}{2}$)，表示边的数量。在接下来的 $m$ 行中，每行输出两个整数 $u_i, v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$)，表示顶点 $u_i$ 和 $v_i$ 之间的一条边。

所有边必须互不相同。该图必须是连通的。

你可以以任意大小写形式输出 YES 和 NO（例如，字符串 yEs, yes, Yes 均被视为肯定回答）。

样例

输入 1

3
3
011
101
110
4
0100
1000
0001
0010
5
01010
10101
01010
10101
01010

输出 1

YES
3
1 2
1 3
2 3
NO
YES
4
1 2
2 3
3 4
4 5

说明

在第一个测试用例中，存在一个包含三个顶点的图——你可以直接取一个三角形。所有两两距离均为 1，因此都是奇数。

可以证明在第二个测试用例中，不存在这样的图。

在第三个测试用例中，我们有一个边为 $(1, 2), (2, 3), (3, 4), (4, 5)$ 的链。在该图中，顶点 $i, j$ 之间的距离为奇数，当且仅当 $i$ 和 $j$ 的奇偶性不同。