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.

Connect Connect See

Examples