A16584 | Customer Service

现在有共 $n$ 条队列，每条队列一开始都有 $0$ 个人。在接下来的 $n$ 个时刻，每个时刻会发生以下两件事（顺序发生）：

1. 在第 $j$ 个时刻，第 $i$ 个队伍的人数增加 $a_{i,j}$；

2. 你可以且必须选择 $n$ 条队列中的一条，并使该队列人数清零。

最后，记第 $i$ 条队列的剩余人数为 $x_i$，请你确定集合 $\{x_1,x_2,\cdots,x_n\}$ 的 $\operatorname{MEX}^{\dagger}$ 可能的最大值。

$^{\dagger}$ 一个集合的 $\operatorname{MEX}$ 是指这个集合所不包含的最小非负整数。

例如：

- $\operatorname{MEX}([2,2,1])=0$，因为 $0$ 不包含于此集合。
- $\operatorname{MEX}⁡([3,1,0,1])=2$，因为 $0$ 与 $1$ 均包含于该集合，但 $2$ 不包含于此集合。
- $\operatorname{MEX⁡([0,3,1,2])}$，因为 $0$、$1$、$2$、$3$ 均包含于该集合，但 $4$ 不包含于此集合。

每个测试点包含多组测试。输入第一行包含一个整数 $t$（$1 \le t \le 2 \times 10^4$），表示该测试点的测试组数。

每个测试组的第一行包含一个整数 $n$（$1 \le n \le 300$），表示队列数与时刻数。

接下来的 $n$ 行每行包括 $n$ 个整数， 第 $i$ 行 $a_{i,1}, a_{i,2}, \ldots, a_{i,n}$（$1 \le a_{i,j} \le 10^9$）表示第 $i$ 个队列在每个时刻的人数增量。

保证每个测试点的所有 $n^2$ 加和不超过 $2 \times 10^5$。

对于每组测试，输出一个整数，表示 $\operatorname{MEX}([x_1, x_2, \ldots, x_n])$ 可达到的最大值。