Diagonal Fancy

Problem Description

Given a matrix $A$ with $n$ rows and $m$ columns, your objective is to compute the total number of continuous sub-square matrices $B$ that are diagonal fancy . A square matrix $B$ is designated as diagonal fancy if it satisfies the subsequent criteria: For any indices $i_1$, $j_1$, $i_2$, and $j_2$, if $i_1 - j_1 = i_2 - j_2$, then $B_{i_1,j_1} = B_{i_2,j_2}$. For any indices $i_1$, $j_1$, $i_2$, and $j_2$, if $i_1 - j_1 \neq i_2 - j_2$, then $B_{i_1,j_1} \neq B_{i_2,j_2}$. Here, $B_{i,j}$ signifies the element located at the $i$-th row and $j$-th column of matrix $B$. A continuous sub-square matrix from matrix $A$ with $n$ rows and $n$ columns is defined as the matrix derived from $A$ by selecting continuous $n$ rows and continuous $n$ columns.

Input

Ensure to use cin/cout and disable synchronization with stdio to avoid unexpected TLE verdict. The input consists of multiple test cases. The first line of the input contains an integer $T$ ($1 \leq T \leq 100$), which represents the number of test cases. The first line of each test case contains two integers $n$ and $m$ ($1 \leq n, m \leq 1000$), representing the number of rows and columns in the matrix $A$. Each of the next $n$ lines contains $m$ space-separated integers $A_{i,1}, A_{i,2}, \ldots, A_{i,m}$ ($1 \leq A_{i,j} \leq n \times m$), representing the elements of the matrix $A$ for that particular test case. It is guaranteed that $\sum n\times m\le 10^7$ over all test cases.

Output

For each test case, output a single integer in a single line, which represents the count of continuous sub-square matrices in matrix $A$ that are diagonal fancy.

Sample Input

3
2 2
1 2
3 1
2 2
1 2
2 1
3 3
1 2 3
4 1 2
5 4 1

Sample Output

5
4
14

Hint

In the first test case, there are $5$ diagonal fancy subsquares in total. They are listed in bold below.

$$\begin{align} &\textbf{1}\text{ }2&\ \ \ \ &1\text{ }\textbf{2}&\ \ \ \ &1\text{ }2&\ \ \ \ &1\text{ }2&\ \ \ \ &\textbf{1}\text{ }\textbf{2}&\notag\newline &3\text{ }1&\ \ \ \ &3\text{ }1&\ \ \ \ &\textbf{3}\text{ }1&\ \ \ \ &3\text{ }\textbf{1}&\ \ \ \ &\textbf{3}\text{ }\textbf{1}&\notag \end{align} $$

Source

2023“钉耙编程”中国大学生算法设计超级联赛（8）