CF1619D.New Year's Problem

Vlad has $n$ friends, for each of whom he wants to buy one gift for the New Year.

There are $m$ shops in the city, in each of which he can buy a gift for any of his friends. If the $j$-th friend ($1 \le j \le n$) receives a gift bought in the shop with the number $i$ ($1 \le i \le m$), then the friend receives $p_{ij}$ units of joy. The rectangular table $p_{ij}$ is given in the input.

Vlad has time to visit at most $n-1$ shops (where $n$ is the number of friends). He chooses which shops he will visit and for which friends he will buy gifts in each of them.

Let the $j$-th friend receive $a_j$ units of joy from Vlad's gift. Let's find the value $\alpha=\min{a_1, a_2, \dots, a_n}$. Vlad's goal is to buy gifts so that the value of $\alpha$ is as large as possible. In other words, Vlad wants to maximize the minimum of the joys of his friends.

For example, let $m = 2$, $n = 2$. Let the joy from the gifts that we can buy in the first shop: $p_{11} = 1$, $p_{12}=2$, in the second shop: $p_{21} = 3$, $p_{22}=4$.

Then it is enough for Vlad to go only to the second shop and buy a gift for the first friend, bringing joy $3$, and for the second — bringing joy $4$. In this case, the value $\alpha$ will be equal to $\min{3, 4} = 3$

Help Vlad choose gifts for his friends so that the value of $\alpha$ is as high as possible. Please note that each friend must receive one gift. Vlad can visit at most $n-1$ shops (where $n$ is the number of friends). In the shop, he can buy any number of gifts.

弗拉德有 $n$ 个朋友，他想为每位朋友各买一份新年礼物。

城市里共有 $m$ 家商店，每家商店均可为任意一位朋友购买礼物。若第 $j$ 位朋友（$1 \le j \le n$）收到在编号为 $i$ 的商店（$1 \le i \le m$）购买的礼物，则该朋友获得 $p_{ij}$ 单位的快乐值。输入中会给出一个大小为 $n \times m$ 的矩形表格 $p_{ij}$。

弗拉德最多只能访问 $n-1$ 家商店（其中 $n$ 为朋友人数）。他需要自行决定访问哪些商店，并在每家商店中为哪些朋友购买礼物。

设第 $j$ 位朋友从弗拉德赠送的礼物中获得 $a_j$ 单位的快乐值。定义 $\alpha = \min\{a_1, a_2, \dots, a_n\}$。弗拉德的目标是使 $\alpha$ 尽可能大，即最大化所有朋友所获快乐值中的最小值。

例如，设 $m = 2$，$n = 2$。第一家商店可提供的礼物快乐值为：$p_{11} = 1$，$p_{12} = 2$；第二家商店可提供的礼物快乐值为：$p_{21} = 3$，$p_{22} = 4$。

此时，弗拉德只需访问第二家商店：为第一位朋友购买快乐值为 $3$ 的礼物，为第二位朋友购买快乐值为 $4$ 的礼物。此时 $\alpha = \min\{3, 4\} = 3$。

请帮助弗拉德为其朋友们挑选礼物，使得 $\alpha$ 尽可能大。注意：每位朋友必须恰好收到一份礼物；弗拉德最多只能访问 $n-1$ 家商店（其中 $n$ 为朋友人数）；在某一家商店中，他可以购买任意数量的礼物。

The first line of the input contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases in the input.

An empty line is written before each test case. Then there is a line containing integers $m$ and $n$ ($2 \le n$, $2 \le n \cdot m \le 10^5$) separated by a space — the number of shops and the number of friends, where $n \cdot m$ is the product of $n$ and $m$.

Then $m$ lines follow, each containing $n$ numbers. The number in the $i$-th row of the $j$-th column $p_{ij}$ ($1 \le p_{ij} \le 10^9$) is the joy of the product intended for friend number $j$ in shop number $i$.

It is guaranteed that the sum of the values $n \cdot m$ over all test cases in the test does not exceed $10^5$.

输入的第一行包含一个整数 $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$ 个数字。第 $i$ 行第 $j$ 列的数字 $p_{ij}$（$1 \le p_{ij} \le 10^9$）表示在第 $i$ 家商店中、为第 $j$ 位朋友准备的商品所带来的快乐值。

保证所有测试用例中 $n \cdot m$ 的总和不超过 $10^5$。

Print $t$ lines, each line must contain the answer to the corresponding test case — the maximum possible value of $\alpha$, where $\alpha$ is the minimum of the joys from a gift for all of Vlad's friends.

输出 $t$ 行，每行必须包含对应测试用例的答案——即 $\alpha$ 的最大可能值，其中 $\alpha$ 是 Vlad 的所有朋友从礼物中获得的喜悦值中的最小值。