Magical Tournament Winner

In the magical realm, creatures participate in a tournament where each pair of contestants face each other. For each match between creature (i) and creature (j), a matrix value (a_{ij}) is given which quantifies the power level of creature (i) against creature (j) (with (a_{ii} = 0)). The winner of a contest is determined by an iterative comparison: start with creature 0 as the current champion, and for every creature (i) from 1 to (n-1), compute the total power level against all other creatures (i.e. (\sum_{j \neq i} a_{ij})). If creature (i) has a strictly greater total power than the current champion, it becomes the new champion. In the case of a tie, the current champion remains. Your task is to simulate this process and output the index of the tournament winner for each test case.

inputFormat

The input is given via standard input (stdin) and has the following format:\ The first line contains an integer (T) representing the number of test cases. For each test case, the first line contains an integer (n) ((1 \leq n \leq 1000)) which indicates the number of creatures. Then follow (n) lines, each containing (n) space-separated integers. The (j)-th number of the (i)-th line represents the power level (a_{ij}) of creature (i) against creature (j). It is guaranteed that (a_{ii} = 0) for all (i).

outputFormat

For each test case, output a single line displaying the index of the tournament winner. The result for each test case should be printed on a separate line to standard output (stdout).## sample

1
3
0 10 20
10 0 30
20 30 0

2