D. Master of the Arena
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are the master of an arena with $$$n$$$ fighters under your control, numbered from $$$1$$$ to $$$n$$$. Fighter $$$1$$$ is your favourite—you want them to emerge as the sole champion.

You are given an $$$n\times n$$$ matrix $$$M$$$. For $$$i\neq j$$$:

  • $$$M_{i,j}=\texttt{1}$$$ means fighter $$$i$$$ definitely beats fighter $$$j$$$.
  • $$$M_{i,j}=\texttt{0}$$$ means fighter $$$i$$$ definitely loses to fighter $$$j$$$.
  • $$$M_{i,j}=\texttt{?}$$$ means the outcome is undecided and you may choose it.

It is guaranteed that $$$M_{i,i} = \texttt{0}$$$ for all $$$i$$$, and for all $$$i \ne j$$$, the pair $$$(M_{i,j}, M_{j,i})$$$ is one of: $$$(\texttt{1}, \texttt{0})$$$, $$$(\texttt{0}, \texttt{1})$$$, or $$$(\texttt{?}, \texttt{?})$$$.

You must schedule exactly $$$n-1$$$ one-on-one matches so that in the end exactly one fighter remains undefeated, and that fighter must be number $$$1$$$. A fighter may appear in multiple matches (until eliminated).

Decide any choices for the '?' entries and output a sequence of $$$n-1$$$ matches $$$(a,b)$$$ meaning "$$$a$$$ defeats $$$b$$$". If it's impossible to make fighter 1 the unique champion, print $$$\textbf{No}$$$.

Input

The first line contains a single integer $$$t$$$ $$$(1 \le t \le 500)$$$ — the number of test cases.

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

Then in each test case follow $$$n$$$ lines each with a string of length $$$n$$$, the $$$i$$$-th line being $$$M_{i,1}M_{i,2}\dots M_{i,n}$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$1000$$$.

Output

In each test case, if it is impossible to guarantee fighter $$$1$$$ wins, print $$$\textbf{No}$$$. Otherwise, print $$$\textbf{Yes}$$$ followed by $$$n - 1$$$ lines. Each line should contain two integers $$$a$$$ and $$$b$$$ indicating that fighter $$$a$$$ defeats fighter $$$b$$$ in a scheduled match. You may print each character in either case, for example $$$\textbf{YES}$$$ and $$$\textbf{yEs}$$$ will also be accepted.

Example
Input
3
3
010
001
100
5
01000
00100
100?0
11?01
11100
5
01000
00100
10000
11101
11100
Output
Yes
2 3
1 2

Yes
4 5
3 4
2 3
1 2

No