問題文

Alice には $N$ 種類、Bob には $M$ 種類の行動があります。 Alice が行動 $i\ (1 \leq i \leq N)$ を、Bob が行動 $j\ (1 \leq j \leq M)$ を選んだとき、スコアは $A_{i,j}$ になります。 ここで、$A_{i,j}$ は負であることもあります。

このゲームは以下の手順で行われます。

1. Alice が、自身の各行動を選ぶ確率（確率分布）を決める。
2. Bob が、Alice の決めた確率分布を知った上で、自身の各行動を選ぶ確率を決める。
3. 両者が、各自の決めた確率分布に従って、互いに独立に行動を $1$ つ選ぶ。

Alice が行動 $i$ を選ぶ確率を $p_i$、Bob が行動 $j$ を選ぶ確率を $q_j$ とすると、スコアの期待値は

$$\sum_{i=1}^{N}\sum_{j=1}^{M}p_iq_jA_{i,j}$$

です。ただし $p_i, q_j \geq 0$、$\sum_{i=1}^{N} p_i = 1$、$\sum_{j=1}^{M} q_j = 1$ です。

Alice はスコアの期待値を最大化しようとし、Bob はスコアの期待値を最小化しようとします。 Alice が最適な確率分布を選び、それに対して Bob も最適な確率分布を選んだ場合のスコアの期待値、すなわち

$$ \max_{\substack{p_i\geq0\\\sum_{i=1}^{N} p_i=1}} \min_{\substack{q_j\geq0\\\sum_{j=1}^{M} q_j=1}} \sum_{i=1}^{N}\sum_{j=1}^{M}p_iq_jA_{i,j} $$

を求めてください。

$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。
※サンプル以外の各テストケースの $A_{i,j}$ はランダムに生成された値です。詳細は「入力の生成方法」の項を確認してください。

入力

入力は以下の形式で標準入力から与えられます。

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

$\mathrm{case}_k$ は $k$ 番目のテストケースを表し、形式は以下の通りです。

$N\ M$
$A_{1,1}\ A_{1,2}\ \ldots\ A_{1,M}$
$A_{2,1}\ A_{2,2}\ \ldots\ A_{2,M}$
$\vdots$
$A_{N,1}\ A_{N,2}\ \ldots\ A_{N,M}$

制約

• $1\leq T\leq 20$
• $1\leq N,M\leq 200$
• $1$ つの入力に含まれる全テストケースに対する $N\times M$ の総和は $200000$ 以下
• $-10000\leq A_{i,j}\leq 10000$
• 入力される値はすべて整数

入力の生成方法

$T$ および各テストケースの $N, M$ は制約の範囲内で定められています。
サンプル以外のテストケースにおいて、各 $A_{i,j}$ は整数区間 $[-10000, 10000]$ から互いに独立かつ一様に選ばれた値です。
なお、ジャッジに使用されるテストケースは固定されています。

出力

$T$ 行出力してください。$k$ 行目には、$k$ 番目のテストケースにおいて両者が最適な確率分布を選んだ場合の、スコアの期待値を出力してください。

ジャッジが保持する基準値は、真の値との絶対誤差が $10^{-10}$ 以下であることが保証されています。

出力した値と基準値との絶対誤差または相対誤差が $10^{-6}$ 以下であれば正解と判定されます。

出力の末尾に改行してください。

サンプル

3
1 1
3
2 2
1 -1
-1 1
2 2
-1 -4
-3 -2

3.0
0.0
-2.5