Consider an array $$$a$$$ consisting of $$$n$$$ distinct integers. The Cartesian Tree of $$$a$$$ is defined as a unique binary tree$$$^{\text{∗}}$$$ that satisfies the following conditions:

The tree consists of $$$n$$$ vertices labeled from $$$1$$$ to $$$n$$$;
For all pairs of vertices $$$(i,j)$$$ such that $$$i$$$ is a parent$$$^{\text{†}}$$$ of $$$j$$$, $$$a_i \gt a_j$$$;
For any vertex $$$i$$$, all vertices in the left subtree$$$^{\text{‡}}$$$ of $$$i$$$ have labels less than $$$i$$$;
For any vertex $$$i$$$, all vertices in the right subtree of $$$i$$$ have labels greater than $$$i$$$.

Denote $$$r(a)$$$ as the root of the Cartesian Tree, and $$$f_a(i)$$$ as the parent of $$$i$$$ in the Cartesian Tree.

Define $$$E_a=\{(i,f_a(i)) \mid 1 \le i \le n, i \ne r(a)\}$$$.

Consider a permutation$$$^{\text{§}}$$$ $$$q$$$ of length $$$n$$$. We define a series of arrays $$$p_1,p_2,\ldots,p_n$$$ as follows:

$$$p_1=q$$$;
For each $$$2 \le i \le n$$$, $$$p_i$$$ is obtained by incrementing the minimum element in $$$p_{i-1}$$$ by $$$n$$$. It can be shown that all elements in $$$p_i$$$ are distinct.

You are now given $$$n$$$ and $$$S=\bigcup\limits_{i=1}^n E_{p_i}$$$. To minimize input, $$$S$$$ will be given in the form of a $$$n \times n$$$ binary matrix $$$s$$$. Denote $$$s_{i,j}$$$ as the $$$j$$$-th character of the $$$i$$$-th row. $$$s_{i,j}=1$$$ if and only if $$$(i,j) \in S$$$.

Please find any permutation $$$q$$$ such that $$$S$$$ can be obtained by the process above. It is guaranteed that the tests are generated to ensure a valid $$$q$$$ always exists.

$$$^{\text{∗}}$$$A binary tree is a rooted tree, in which each node has no more than $$$2$$$ children, referred to as the left child and the right child.

$$$^{\text{†}}$$$The parent of vertex $$$v$$$ is the first vertex on the simple path from $$$v$$$ to the root. The root has no parent.

$$$^{\text{‡}}$$$A subtree of vertex $$$v$$$ is the subgraph of $$$v$$$, all its descendants, and all the edges between them.

$$$^{\text{§}}$$$A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

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 contains an integer $$$n$$$ ($$$2 \le n \le 3000$$$) — the length of $$$q$$$ that you need to find.

The $$$i$$$-th of the next $$$n$$$ lines contains a binary string of length $$$n$$$, representing the $$$i$$$-th row of $$$s$$$. It is guaranteed that $$$s_{i,i} = 0$$$ for all $$$1 \le i \le n$$$.

It is guaranteed that the tests are generated to ensure a valid $$$q$$$ always exists.

It is guaranteed that the sum of $$$n^2$$$ over all test cases does not exceed $$$9 \cdot 10^6$$$.

Output

For each test case, output $$$n$$$ integers $$$q_1,q_2,\ldots,q_n$$$, representing the permutation $$$q$$$ you found.

Note

$\text{[math]}$

Many Cartesian Trees

Examples