"For problems you don’t know how to solve, just submit something random. Who knows, maybe it will pass."

Given an $n \times m$ matrix of numbers, you may arbitrarily rearrange the numbers in each row so that the sum of the minimum values of all columns is maximized.

Formally, let the rearranged matrix be $A$. Maximize $\sum_{j=1}^m (\min_{i=1}^n A_{i,j})$.

You need to output this maximum value.

"More often than not, things going against our wishes is simply the norm in life."

Input

The first line of the input contains the number of test cases $T$ ($1 \leq T \leq 10^5$).

For each test case, the first line contains two positive integers $n, m$ ($1 \leq n, m \leq 1000$), representing the size of the matrix.

The next $n$ lines each contain $m$ integers, representing the numbers $A_{i,j}$ in the matrix ($0 \leq A_{i,j} \leq 10^9$).

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

Output

For each test case, output a single integer on one line representing the answer.

Examples

Input 1

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

Output 1

5
5
4