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: