Descrizione

"Per i problemi che non sai come risolvere, invia semplicemente qualcosa a caso. Chissà, magari passerà."

Data una matrice di numeri di dimensione $n \times m$, puoi riordinare arbitrariamente i numeri in ciascuna riga in modo che la somma dei valori minimi di tutte le colonne sia massimizzata.

Formalmente, sia $A$ la matrice riordinata. Massimizza $\sum_{j=1}^m (\min_{i=1}^n A_{i,j})$.

Devi stampare questo valore massimo.

"Il più delle volte, che le cose vadano contro i nostri desideri è semplicemente la norma nella vita."

Input

La prima riga dell'input contiene il numero di casi di test $T$ ($1 \leq T \leq 10^5$).

Per ciascun caso di test, la prima riga contiene due interi positivi $n, m$ ($1 \leq n, m \leq 1000$), che rappresentano la dimensione della matrice.

Le successive $n$ righe contengono ciascuna $m$ interi, che rappresentano i numeri $A_{i,j}$ nella matrice ($0 \leq A_{i,j} \leq 10^9$).

È garantito che la somma di $n \cdot m$ su tutti i casi di test non supera $10^6$.

Output

Per ciascun caso di test, stampa un singolo intero su una riga che rappresenta la risposta.

Esempi

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