CF2059C Customer Service

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.

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

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.

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