“对于你不会做的题，随便交点随机的东西上去。谁知道呢，说不定就过了。”

给定一个 $n \times m$ 的数字矩阵，你可以任意重新排列每一行中的数字，使得所有列的最小值之和最大。

正式地，设重排后的矩阵为 $A$。最大化 $\sum_{j=1}^{m} \left(\min_{i=1}^{n} A_{i,j}\right)$。

你需要输出这个最大值。

“很多时候，事情与我们的愿望背道而驰，这只是生活中的常态。”

输入格式

输入的第一行包含测试用例的数量 $T$ ($1 \le T \le 10^5$)。

对于每个测试用例，第一行包含两个正整数 $n, m$ ($1 \le n, m \le 1000$)，表示矩阵的大小。

接下来的 $n$ 行，每行包含 $m$ 个整数，表示矩阵中的数字 $A_{i,j}$ ($0 \le A_{i,j} \le 10^9$)。

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

输出格式

对于每个测试用例，在单独的一行中输出一个整数，表示答案。

样例

输入样例 1

3
1 1
5
2 2
1 4
2 5
3 3
1 2 1
2 2 1
1 1 2

输出样例 1

5
5
4