Welcome to ZOJ Contests Information Problems Runs Statistics Ranklist Clarification 147 - The 17th Zhejiang University Programming Contest Sponsored by TuSimple - H

Time Limit: 1 Second      Memory Limit: 131072 KB

Chiaki has an n × m matrix A. Rows are numbered from 1 to n from top to bottom and columns are numbered from 1 to m from left to right. The element in the i-th row and the j-th column is Ai, j.

Let M({i1, i2, ..., is}, {j1, j2, ..., jt}) be the matrix that results from deleting row i1, i2, ..., is and column j1, j2, ..., jt of A and f({i1, i2, ..., is}, {j1, j2, ..., jt}) be the number of saddle points in matrix M({i1, i2, ..., is}, {j1, j2, ..., jt}).

Chiaki would like to find all the value of f({i1, i2, ..., is}, {j1, j2, ..., jt}). As the output may be very large ((2n - 1)(2m - 1) matrix in total), she is only interested in the value Note that a saddle point of a matrix is an element which is both the only largest element in its column and the only smallest element in its row.

#### Input

There are multiple test cases. The first line of input contains an integer T, indicating the number of test cases. For each test case:

The first line contains four integers n and m (1 ≤ n, m ≤ 1000) -- the number of rows and the number of columns.

Each of the next n lines contains m integer Ai, 1, Ai, 2, ..., Ai, m (1 ≤ Ai, j ≤ 106), where Ai, j is the integer in the i-th row and the j-th column.

It is guaranteed that neither the sum of all n nor the sum of all m exceeds 5000.

#### Output

For each test case, output an integer denoting the answer.

#### Sample Input

2
2 2
1 1
1 1
4 5
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20


#### Sample Output

4
465


Submit    Status