「解き方がわからない問題には、適当に何かを提出してみよう。もしかしたら通るかもしれない。」

$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