You are given a rectangular grid $a$ consisting of $n$ rows and $m$ columns. The $j$-th cell in the $i$-th row is denoted by $(i,j)$. There is a non-negative integer written in every cell. The integer written in cell $(i,j)$ is denoted by $a_{i,j}$.

A path $p$ of length $k$ on $a$ is defined as a sequence of cells $p_0,p_1,\ldots,p_k$ such that $p_i$ and $p_{i+1}$ share an edge for every $0 \le i \lt k$, and all $p_i$ are distinct. The number of turns of a simple path $p$ of length $k$, denoted by $t(p)$, is defined as the number of indices $1 \le i \lt k$ that satisfy the following condition:

• Let $p_j=(x_j,y_j)$ for $j \in \{i-1,i,i+1\}$. Then, both $x_{i-1} \ne x_{i+1}$ and $y_{i-1} \ne y_{i+1}$ hold.

A path $p=[(x_0,y_0),(x_1,y_1),\ldots,(x_k,y_k)]$ is considered valid if and only if all of the following conditions hold:

• $k \ge 1$.
• $t(p) \le 2$.
• $a_{x_0,y_0}=a_{x_k,y_k}$, $a_{x_0,y_0} \gt 0$, and $a_{x_i,y_i}=0$ for every $1 \le i \lt k$.

An unordered pair of cells $(u_1,v_1)$ and $(u_2,v_2)$ is considered connectable if and only if there exists a valid path $p$ of length $k$ such that $p_0=(u_1,v_1)$ and $p_k=(u_2,v_2)$.

Find the number of connectable pairs in $a$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($1 \le n \le 100$, $1 \le n \cdot m \le 2 \cdot 10^6$), representing the dimensions of $a$.

The $i$-th of the next $n$ lines contains $m$ integers $a_{i,1}, a_{i,2},\ldots,a_{i,m}$ ($0 \le a_{i,j} \le n \cdot m$), representing the $i$-th row of $a$.

It is guaranteed that the sum of $n \cdot m$ over all test cases does not exceed $2 \cdot 10^6$.

Output

For each test case, output an integer representing the number of connectable pairs in $a$.

Note

In the first and second test cases, there are no connectable pairs in $a$.

In the third test case, the connectable pairs are:

• $(1,1),(1,2)$.
• $(1,2),(2,2)$.
• $(1,1),(2,2)$.

In the sixth test case, there are $34$ connectable pairs. One of them is $(1,1),(3,3)$. Note that $(1,1),(5,5)$ is not a connectable pair, as any path that begins at $(1,1)$ and ends at $(5,5)$ has more than $2$ turns.