“풀 줄 모르는 문제는 그냥 아무거나 제출해 봐. 누가 알아, 통과할지도 모르잖아.”

$n \times m$ 숫자 행렬이 주어진다. 각 행의 수들을 자유롭게 재배열하여 모든 열의 최솟값의 합을 최대화할 수 있다.

형식적으로, 재배열한 행렬을 $A$라 하자. $\sum_{j=1}^m (\min_{i=1}^n A_{i,j})$를 최대화하라.

이 최댓값을 출력해야 한다.

“일이 뜻대로 되지 않는 것이 인생에서는 오히려 일상인 경우가 많다.”

입력

입력의 첫 번째 줄에는 테스트 케이스의 개수 $T$ ($1 \leq T \leq 10^5$)가 주어진다.

각 테스트 케이스의 첫 번째 줄에는 행렬의 크기를 나타내는 두 양의 정수 $n, m$ ($1 \leq n, m \leq 1000$)이 주어진다.

다음 $n$개의 줄에는 각각 $m$개의 정수가 주어지며, 행렬의 수 $A_{i,j}$를 나타낸다 ($0 \leq A_{i,j} \leq 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