You are given an $N \times M$ matrix $A[1..N][1..M]$. We say that $(x_1,y_1)$ controls $(x_2,y_2)$ if and only if $A[x_1][y_1] > A[x_2][y_2] + |x_1-x_2| + |y_1-y_2|$. Now you need to calculate the number of pairs $((x_1,y_1),(x_2,y_2))$ that $(x_1,y_1)$ controls $(x_2,y_2)$.
输入解释
There are multiple test cases.
For each test case, the first line contains two integers $N$ and $M$, denoting the size of the matrix.
Then there are $N$ lines denoting the matrix, where each line contains $M$ integers.
$1\leq N,M \leq 10^3, ~ 1\leq A[i][j] \leq N+M$. And the sum of $N \times M$ of all test cases is not larger than $2 \cdot 10^6$.
输出解释
For each test case, print an integer in one line, denoting your answer.