This is the hard version of the problem. The difference between the versions is that in this version, the constraint on $n$ is higher. You can hack only if you solved all versions of this problem.

You once had an undirected tree with $n$ nodes. To make the tree look more interesting, you decided to assign an arbitary direction to each of the $n-1$ edges.

As time goes by, you forgot the structure of your tree. However, you found a note which recorded after the direction of the edges have been assigned, whether $u$ can reach $v$$^{\text{∗}}$ for all ordered pairs of $(u,v)$ which satisfies $1\le u,v\le n$.

You want to find out the structure of the tree and the direction of the edges from the information given by the note. Determine if there is possible solution and construct one. If there are multiple solutions, you only need to find one of them.

$^{\text{∗}}$For a directed graph, we say that $x$ can reach $y$ if and only if there exists a sequence of nodes $u_1,u_2,\ldots,u_k$ such that $u_1=x,u_k=y$ and for all $i$ from $2$ to $k$, the directed edge $u_{i-1}\rightarrow u_i$ exists. In particular, a node can always reach itself.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test cases contain an integer $n$ ($2\le n\le 8000$) denoting the number of nodes your tree have.

The following $n$ lines contain a string $s_i$. $s_i$ is of length $n$ and consists only of $0$ and $1$. The $j$-th character of $s_i$ is $1$ if and only if $i$ can reach $j$ after the edges are directed.

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

Output

For each testcase, output $\texttt{Yes}$ if a solution exists, otherwise print $\texttt{No}$. If the answer is $\texttt{Yes}$, on the following lines output a description of the edges constructed.

Output $n-1$ lines denoting the directed edges. Each line should contain two integers $x$ and $y$, denoting that after the edges are directed, the directed edge $x\rightarrow y$ exists. If there are multiple solutions, print any of them.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

Note

For the first test case, nodes $1$ and $4$ can only reach themselves, node $2$ can reach every node, node $3$ can only reach node $1$ and $3$. The constructed edges satisfy this constraint.

For the second test case, it can be proven that no possible solution exists.