Vlad 有 $$$n$$$ 个朋友,他想为每个人买一份新年礼物。
城里有 $$$m$$$ 商店,他可以在每个商店里为他的任何朋友购买礼物。如果第 $$$j$$$ 位朋友 ($$$1 \le j \le n$$$) 收到在商店购买的礼物,编号为 $$$i$$$ ($$$1 \le i \le m$$$),则该朋友将收到 $$$p_{ij}$$$ 单位的快乐。输入中给出了矩形表 $$$p_{ij}$$$。
Vlad 有时间最多访问 $$$n-1$$$ 商店(其中 $$$n$$$ 是朋友的数量)。他选择要参观哪些商店以及在每家商店为哪些朋友购买礼物。
让第 $$$j$$$ 个朋友从 Vlad 的礼物中获得 $$$a_j$$$ 单位的快乐。让我们找到值 $$$\alpha=\min\{a_1, a_2, \dots, a_n\}$$$。 Vlad 的目标是购买礼物,使 $$$\alpha$$$ 的价值尽可能大。换句话说,弗拉德想要最大化他朋友们最小的快乐。
例如,让$$$m = 2$$$,$$$n = 2$$$。让我们享受在第一家商店可以买到的礼物:$$$p_{11} = 1$$$,$$$p_{12}=2$$$,在第二家商店:$$$p_{21} = 3$$$,$$$p_{22}=4$$$。
那么 Vlad 只需要去第二家商店为第一个朋友买一份礼物,带来欢乐 $$$3$$$,为第二个朋友买礼物 - 带来欢乐 $$$4$$$。在这种情况下,值 $$$\alpha$$$ 将等于 $$$\min\{3, 4\} = 3$$$
帮助 Vlad 为他的朋友选择礼物,使 $$$\alpha$$$ 的价值尽可能高。请注意,每位朋友必须收到一份礼物。 Vlad 最多可以访问 $$$n-1$$$ 商店(其中 $$$n$$$ 是朋友的数量)。在商店里,他可以购买任意数量的礼物。
输入
输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 输入中测试用例的数量。
每个测试用例之前写入一个空行。然后有一行包含整数 $$$m$$$ 和 $$$n$$$ ($$$2 \le n$$$, $$$2 \le n \cdot m \le 10^5$$$),并用空格分隔 — 商店数量和朋友数量,其中 $$$n \cdot m$$$ 是 $$$n$$$ 和 $$$m$$$ 的乘积。
接下来是 $$$m$$$ 行,每行包含 $$$n$$$ 数字。 $$$j$$$第$$$p_{ij}$$$第$$$i$$$行的数字($$$1\le p_{ij}\le 10^9$$$)是$$$i$$$店号中给朋友$$$j$$$预定的商品的喜悦度。
保证测试中所有测试用例的值 $$$n \cdot m$$$ 之和不超过 $$$10^5$$$。
输出
打印 $$$t$$$ 行,每行必须包含相应测试用例的答案 - $$$\alpha$$$ 的最大可能值,其中 $$$\alpha$$$ 是给 Vlad 所有朋友的礼物带来的最小快乐。
示例
输入 #1
5 2 2 1 2 3 4 4 3 1 3 1 3 1 1 1 2 2 1 1 3 2 3 5 3 4 2 5 1 4 2 7 9 8 1 9 6 10 8 2 4 6 5 2 1 7 9 7 2
输出 #1
3 2 4 8 2