给定一个整数矩阵,其中包含 $$$n$$$ 行和 $$$m$$$ 列。第 $$$i$$$ 行和第 $$$j$$$ 列交叉处的单元格包含数字 $$$a_{ij}$$$。
您可以执行以下操作 正好一次:
- 选择两个数字 $$$1 \leq r \leq n$$$ 和 $$$1 \leq c \leq m$$$。
- 对于矩阵中满足 $$$i = r$$$ 或 $$$j = c$$$ 的所有单元格 $$$(i, j)$$$,将 $$$a_{ij}$$$ 减一。
在执行一次此类操作后,您需要找到矩阵 $$$a$$$ 中的最小可能最大值。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq n \cdot m \leq 10^5$$$) - 矩阵中的行数和列数。
每个测试用例的接下来 $$$n$$$ 行描述矩阵 $$$a$$$。第 $$$i$$$ 行包含 $$$m$$$ 整数 $$$a_{i1}, a_{i2}, \ldots, a_{im}$$$ ($$$1 \leq a_{ij} \leq 100$$$) — 矩阵第 $$$i$$$ 行中的元素。
保证所有测试用例的 $$$n \cdot m$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,在执行一次操作后输出矩阵 $$$a$$$ 中的最小最大值。
示例
输入复制
101 111 21 22 1212 24 23 43 41 2 3 23 2 1 32 1 3 24 31 5 13 1 35 5 53 5 14 41 3 3 22 3 2 21 2 2 13 3 2 32 22 21 23 21 22 11 23 32 1 11 2 11 1 2
输出复制
0 1 1 3 2 4 3 1 1 2
注意
在前三个测试用例中,您可以选择 $$$r = 1$$$ 和 $$$c = 1$$$。
在第四个测试用例中,您可以选择 $$$r = 1$$$ 和 $$$c = 2$$$。
在第五个测试用例中,您可以选择 $$$r = 2$$$ 和 $$$c = 3$$$。
在第六个测试用例中,您可以选择 $$$r = 3$$$ 和 $$$c = 2$$$。