Giải bài trực tuyến

Players P1 and P2 are playing a game. The game is played using a matrix M of integers, the size of which is given to be m x n.

In each turn, P1 selects a number i lying between 0 and m-1 (inclusive) while P2 selects a number j lying between 0 and n-1 (again inclusive). The fun part is that each of them remains unaware of what the other has chosen...

After the choices have been finalized, they reveal their numbers to each other. M[i][j] is the element of the matrix decided by the choices the players made. If M[i][j] is Negative, P1 pays P2 an amount equal to the absolute value of M[i][j]. However, if M[i][j] is Positive, then P2 pays P1 an amount equal to M[i][j].

Given the Matrix M and the fact that both the players are infinitely intelligent, find out the average amount paid by P2 to P1 per turn in the game.

Note: P1 plays to maximize the money he gets while P2 tries to minimize the money he has to pay.

Input

First line contains T, the number of test cases.

For each test case the first line contains two integers m and n, denoting the size of the matrix. The next m lines contains n integers each denoting the elements of the matrix.

Output

The output should consist of T lines, each containing a real number with exactly 3 digits precision, denoting the average payoff which P1 receives per turn in the game.

Example

Input:
3
1 1
-1
2 2
1 2
3 4
2 2
1 4
4 3

Output:
-1.000
3.000
3.250

Constraints

Input Set 1: m <= 2, n <= 10, abs(values) <= 150000, numberOfTestCases <= 120.

Input Set 2: m <= 2, n <= 5000, abs(values) <= 150000, numberOfTestCases <= 20.

Input Set 3: m <= 2, n <= 100000, abs(values) <= 150000, numberOfTestCases <= 10.

Input Set 4: m <= 3, n <= 5000, abs(values) <= 150000, numberOfTestCases <= 15.