#P1619D. New Year's Problem

    ID: 151 Type: RemoteJudge 2000ms 256MiB Tried: 0 Accepted: 0 Difficulty: (None) Uploaded By: Tags>binary searchgreedysortings*1800

New Year's Problem

No submission language available for this problem.

Description

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

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

Vlad has time to visit at most n1n-1 shops (where nn 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 jj-th friend receive aja_j units of joy from Vlad's gift. Let's find the value α=min{a1,a2,,an}\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=2m = 2, n=2n = 2. Let the joy from the gifts that we can buy in the first shop: p11=1p_{11} = 1, p12=2p_{12}=2, in the second shop: p21=3p_{21} = 3, p22=4p_{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 33, and for the second — bringing joy 44. In this case, the value α\alpha will be equal to min{3,4}=3\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 n1n-1 shops (where nn is the number of friends). In the shop, he can buy any number of gifts.

The first line of the input contains an integer tt (1t1041 \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 mm and nn (2n2 \le n, 2nm1052 \le n \cdot m \le 10^5) separated by a space — the number of shops and the number of friends, where nmn \cdot m is the product of nn and mm.

Then mm lines follow, each containing nn numbers. The number in the ii-th row of the jj-th column pijp_{ij} (1pij1091 \le p_{ij} \le 10^9) is the joy of the product intended for friend number jj in shop number ii.

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

Print tt 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.

Input

The first line of the input contains an integer tt (1t1041 \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 mm and nn (2n2 \le n, 2nm1052 \le n \cdot m \le 10^5) separated by a space — the number of shops and the number of friends, where nmn \cdot m is the product of nn and mm.

Then mm lines follow, each containing nn numbers. The number in the ii-th row of the jj-th column pijp_{ij} (1pij1091 \le p_{ij} \le 10^9) is the joy of the product intended for friend number jj in shop number ii.

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

Output

Print tt 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.

Samples

Sample Input 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

Sample Output 1

3
2
4
8
2