Hide

Problem F
Kingdoms

Several kingdoms got into serious financial troubles. For many years, they have been secretly borrowing more and more money from each other. Now, with their liabilities exposed, the crash is inevitable…

There are $n$ kingdoms. For each pair $(A, B)$ of kingdoms, the amount of gold that kingdom $A$ owes to kingdom $B$ is expressed by an integer number $d_{AB}$ (we assume that $d_{BA}$ = $-d_{AB}$). If a kingdom has negative balance (has to pay more than it can receive), it may bankrupt. Bankruptcy removes all liabilities, both positive and negative, as if the kingdom ceased to exist. The next kingdom may then bankrupt, and so on, until all remaining kingdoms are financially stable.

Depending on who falls first, different scenarios may occur—in particular, sometimes only one kingdom might remain. Determine, for every kingdom, whether it can become the only survivor.

Input

The first line of the input contains the number of test cases $T$, where $1 \le T \le 10\, 000$. The descriptions of the test cases follow:

The description of each test case starts with a line containing the number of the kingdoms $n$, $1 \leq n \leq 20$. Then $n$ lines follow, each containing $n$ space-separated numbers. The $j$-th number in the $i$-th line is the number $d_{ij}$ of gold coins that the $i$-th kingdom owes to the $j$-th one. You may assume that $d_{ii} = 0$ and $d_{ij} = -d_{ji}$ for every $1 \leq i, j \leq n$. Also, $|d_{ij}| \leq 10^{10}$ for all possible $i, j$.

Output

Print the answers to the test cases in the order in which they appear in the input. For each test case, print a single line containing the indices of the kingdoms that can become the sole survivors, in increasing order. If there are no such kingdoms, print a single number 0.

Sample Input 1 Sample Output 1
1
3
0 -3 1
3 0 -2
-1 2 0
1 3

Please log in to submit a solution to this problem

Log in