Nikyr has started working as a queue manager at the company "Black Contour." He needs to choose the order of servicing customers. There are a total of $n$ queues, each initially containing $0$ people. In each of the next $n$ moments of time, there are two sequential events:

1. New customers arrive in all queues. More formally, at the $j$-th moment of time, the number of people in the $i$-th queue increases by a positive integer $a_{i,j}$.
2. Nikyr chooses exactly one of the $n$ queues to be served at that moment in time. The number of customers in this queue becomes $0$.

Let the number of people in the $i$-th queue after all events be $x_i$. Nikyr wants MEX$^{\dagger}$ of the collection $x_1, x_2, \ldots, x_n$ to be as large as possible. Help him determine the maximum value he can achieve with an optimal order of servicing the queues.

$^{\dagger}$The minimum excluded (MEX) of a collection of integers $c_1, c_2, \ldots, c_k$ is defined as the smallest non-negative integer $y$ which does not occur in the collection $c$.

For example:

• $\operatorname{MEX}([2,2,1])= 0$, since $0$ does not belong to the array.
• $\operatorname{MEX}([3,1,0,1]) = 2$, since $0$ and $1$ belong to the array, but $2$ does not.
• $\operatorname{MEX}([0,3,1,2]) = 4$, since $0$, $1$, $2$, and $3$ belong to the array, but $4$ does not.

Input

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 2 \cdot 10^4$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($1 \le n \le 300$) — the number of queues and moments of time.

The $i$-th of the next $n$ lines contains $n$ integers $a_{i,1}, a_{i,2}, \ldots, a_{i,n}$ ($1 \le a_{i,j} \le 10^9$) — the number of new customers in the $i$-th queue at each moment of time.

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

Output

For each test case, output a single integer — the maximum value of $\operatorname{MEX}([x_1, x_2, \ldots, x_n])$ that can be achieved.

Note

In the first test case, the second queue can be served at time $1$, and the first queue at time $2$. There will be $x_1 = 0$ people left in the first queue and $x_2 = 1$ person left in the second queue. Therefore, the answer is $\operatorname{MEX}([0, 1]) = 2$.

In the second test case, the first queue can be served both times. There will be $x_1 = 0$ people left in the first queue and $x_2 = 20$ people left in the second queue. Therefore, the answer is $\operatorname{MEX}([0, 20]) = 1$.

In the third test case, the third queue can be served at time $1$, the second queue at time $2$, and the first queue at time $3$. There will be $x_1 = 0$ people left in the first queue, $x_2 = 1$ person left in the second queue, and $x_3 = 2$ people left in the third queue. Therefore, the answer is $\operatorname{MEX}([0, 1, 2]) = 3$.