CF2059C 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 \cdot 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])$ 可达到的最大值。

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 $ .