C. Обслуживание клиентов
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Никир устроился работать регулировщиком очередей в компанию «Чёрный Контур». Ему нужно будет выбирать порядок обслуживания клиентов. Всего есть $$$n$$$ очередей, в каждой из которых изначально стоит $$$0$$$ человек. В каждый из следующих $$$n$$$ моментов времени происходит два последовательных события:

  1. Во все очереди приходят новые клиенты. Более формально, в $$$j$$$-й момент времени количество людей в $$$i$$$-й очереди увеличивается на положительное целое число $$$a_{i,j}$$$.
  2. Никир выбирает ровно одну из $$$n$$$ очередей, которую будут обслуживать в этот момент времени. Количество клиентов в этой очереди становится равным $$$0$$$.

Пусть количество людей в $$$i$$$-й очереди после всех событий равно $$$x_i$$$. Никир хочет, чтобы MEX$$$^{\dagger}$$$ набора чисел $$$x_1, x_2, \ldots, x_n$$$ был как можно больше. Помогите ему определить максимальное значение, которое он сможет получить при оптимальном порядке обслуживания очередей.

$$$^{\dagger}$$$Наименьшее исключенное (MEX) набора чисел $$$c_1, c_2, \ldots, c_k$$$ определяется как наименьшее неотрицательное целое число $$$y$$$, которое не встречается в наборе чисел $$$c$$$.

Например:

  • $$$\operatorname{MEX}([2,2,1])= 0$$$, так как $$$0$$$ не принадлежит массиву.
  • $$$\operatorname{MEX}([3,1,0,1]) = 2$$$, так как $$$0$$$ и $$$1$$$ принадлежат массиву, а $$$2$$$ нет.
  • $$$\operatorname{MEX}([0,3,1,2]) = 4$$$, так как $$$0$$$, $$$1$$$, $$$2$$$ и $$$3$$$ принадлежат массиву, а $$$4$$$ нет.
Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 300$$$) — количество очередей и моментов времени.

$$$i$$$-я из следующих $$$n$$$ строк содержит $$$n$$$ целых чисел $$$a_{i,1}, a_{i,2}, \ldots, a_{i,n}$$$ ($$$1 \le a_{i,j} \le 10^9$$$) — количество новых клиентов в $$$i$$$-й очереди в каждый из моментов времени.

Гарантируется, что сумма $$$n^2$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите единственное целое число — максимальное значение $$$\operatorname{MEX}([x_1, x_2, \ldots, x_n])$$$, которое можно получить.

Пример
Входные данные
4
2
1 2
2 1
2
10 10
10 10
3
2 3 3
4 4 1
2 1 1
4
4 2 2 17
1 9 3 1
5 5 5 11
1 2 1 1
Выходные данные
2
1
3
3
Примечание

В первом наборе входных данных можно обслужить вторую очередь в момент времени $$$1$$$ и первую очередь в момент времени $$$2$$$. В первой очереди останется $$$x_1 = 0$$$ человек, во второй очереди останется $$$x_2 = 1$$$ человек. Тогда ответ равен $$$\operatorname{MEX}([0, 1]) = 2$$$.

Во втором наборе входных данных можно оба раза обслужить первую очередь. В первой очереди останется $$$x_1 = 0$$$ человек, во второй очереди останется $$$x_2 = 20$$$ человек. Тогда ответ равен $$$\operatorname{MEX}([0, 20]) = 1$$$.

В третьем наборе входных данных можно обслужить третью очередь в момент времени $$$1$$$, вторую очередь в момент времени $$$2$$$ и первую очередь в момент времени $$$3$$$. В первой очереди останется $$$x_1 = 0$$$ человек, во второй очереди останется $$$x_2 = 1$$$ человек, в третьей очереди останется $$$x_3 = 2$$$ человека. Тогда ответ равен $$$\operatorname{MEX}([0, 1, 2]) = 3$$$.