Problem Statement

Alice has $N$ kinds of actions and Bob has $M$ kinds of actions. When Alice chooses action $i\ (1 \leq i \leq N)$ and Bob chooses action $j\ (1 \leq j \leq M)$, the score is $A_{i,j}$. Here, $A_{i,j}$ may be negative.

The game proceeds as follows.

1. Alice decides the probability of choosing each of her actions (a probability distribution).
2. Bob, knowing the probability distribution Alice decided on, decides the probability of choosing each of his actions.
3. Each player chooses $1$ action according to their own probability distribution, independently of each other.

Letting $p_i$ be the probability that Alice chooses action $i$ and $q_j$ be the probability that Bob chooses action $j$, the expected value of the score is

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

where $p_i, q_j \geq 0$, $\sum_{i=1}^{N} p_i = 1$, and $\sum_{j=1}^{M} q_j = 1$.

Alice tries to maximize the expected score, and Bob tries to minimize the expected score. Find the expected score when Alice chooses an optimal probability distribution and Bob chooses an optimal probability distribution in response to it, that is,

$$ \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} $$

.

You are given $T$ test cases; find the answer for each of them.
Note: except for the samples, the values $A_{i,j}$ of each test case are randomly generated. See the "Input Generation" section for details.

Input

The input is given from Standard Input in the following format.

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

$\mathrm{case}_k$ represents the $k$-th test case and is in the following format.

$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}$

Constraints

• $1\leq T\leq 20$
• $1\leq N,M\leq 200$
• The sum of $N\times M$ over all test cases in $1$ input is at most $200000$
• $-10000\leq A_{i,j}\leq 10000$
• All input values are integers

Input Generation

$T$ and the values $N, M$ of each test case are set within the constraints.
In test cases other than the samples, each $A_{i,j}$ is chosen independently and uniformly at random from the integer interval $[-10000, 10000]$.
The test cases used by the judge are fixed.

Output

Output $T$ lines. On the $k$-th line, output the expected score for the $k$-th test case when both players choose optimal probability distributions.

The reference value held by the judge is guaranteed to have an absolute error of at most $10^{-10}$ from the true value.

Your output is judged correct if its absolute or relative error from the reference value is at most $10^{-6}$.

Print a newline at the end of the output.

Sample

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

3.0
0.0
-2.5