Saddle Point

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 `A`_{i, j}.

Let `M`({`i`_{1}, `i`_{2}, ..., `i`_{s}}, {`j`_{1}, `j`_{2}, ..., `j`_{t}}) be the matrix that results from deleting row `i`_{1}, `i`_{2}, ..., `i`_{s} and column `j`_{1}, `j`_{2}, ..., `j`_{t} of `A` and `f`({`i`_{1}, `i`_{2}, ..., `i`_{s}}, {`j`_{1}, `j`_{2}, ..., `j`_{t}}) be the number of saddle points in matrix `M`({`i`_{1}, `i`_{2}, ..., `i`_{s}}, {`j`_{1}, `j`_{2}, ..., `j`_{t}}).

Chiaki would like to find all the value of `f`({`i`_{1}, `i`_{2}, ..., `i`_{s}}, {`j`_{1}, `j`_{2}, ..., `j`_{t}}). As the output may be very large ((2^{n} - 1)(2^{m} - 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 `A`_{i, 1}, `A`_{i, 2}, ..., `A`_{i, m} (1 ≤ `A`_{i, j} ≤ 10^{6}), where `A`_{i, 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