There exist $N$ kingdoms. Each of these $N$ kingdoms is interested in some (can be none or all) of the $M$ resources. If Kingdom $I$ obtains the resource $J$, the global happiness index will increase by some value (let us assume this is $X[I][J]$). Furthermore, no two kingdoms may take the same resource, and a kingdom may take no more than one resource (that is either 0 or 1) from all resources in which it is interested.

Once the kingdoms have obtained their resources, they will construct precisely $N-1$ bridges linking the $N$ kingdoms by a simple path, that is:

• If $N ≥ 2$, exactly two kingdoms will be connected to one another kingdom, and the remaining $N-2$ kingdoms will each be connected to two other kingdoms, thus forming a simple path linking all the $N$ kingdoms. i.e. Each kingdom will be connected to $N-1$ others through bridges, with each node having atmost one child.

Now every two connected kingdoms can partially share their resources through these $N-1$ bridges provided that both kingdoms receive the resource of their interest.

Additionally, this will raise the global happiness index by $(\lfloor X[I1][J2]/2\rfloor + \lfloor X[I2][J1]/2\rfloor)$ (If kingdoms $I1$ and $I2$ have resources $J1$ and $J2$, respectively, are sharing their resources).

Print the maximum global happiness index that can be achieved

 Input Format:

• ​The first line contains a single integer $T$, which denotes the number of test cases. ​
• The first line of each test case contains two integers $N$ and  $M$, which denote the number of kingdoms and the number of resources.
• Each of the next $N$ (1 ≤ I ≤ N)  lines contains $M$ (1 ≤ J ≤ M) integers denoting the value $X[I][J]$.
  • The $I$th line has $J$th integer as $0$ in the case Kingdom $I$ is not interested in the resource $J$, otherwise, it's a positive integer.

Output Format:

For each test case, print the maximum global happiness index that can be achieved, in a new line.

Constraints:

$1 \leq T \leq 10 \\ 1 \leq N \leq 10 \\ 1≤M≤25 \\ 0≤X[I][J]≤10^{15}\ ∀\ I∈[1,N],\ J∈[1,M]$