«Para los problemas que no sabes resolver, envía cualquier cosa al azar. Quién sabe, quizá pase».

Dada una matriz de números de tamaño $n \times m$, puedes reordenar arbitrariamente los números de cada fila para maximizar la suma de los valores mínimos de todas las columnas.

Formalmente, sea $A$ la matriz reordenada. Maximiza $\sum_{j=1}^m (\min_{i=1}^n A_{i,j})$.

Debes imprimir este valor máximo.

«Muy a menudo, que las cosas no salgan como deseamos es simplemente lo habitual en la vida».

Entrada

La primera línea de la entrada contiene el número de casos de prueba $T$ ($1 \leq T \leq 10^5$).

Para cada caso, la primera línea contiene dos enteros positivos $n, m$ ($1 \leq n, m \leq 1000$), que representan el tamaño de la matriz.

Cada una de las siguientes $n$ líneas contiene $m$ enteros, que representan los números $A_{i,j}$ de la matriz ($0 \leq A_{i,j} \leq 10^9$).

Se garantiza que la suma de $n \cdot m$ entre todos los casos no supera $10^6$.

Salida

Para cada caso, imprime en una línea un único entero que represente la respuesta.

Ejemplos

Entrada 1

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

Salida 1

5
5
4