2022 年上海市大学生程序设计竞赛 - 十月赛

C. Moonlight over the Lotus Pond

单点时限: 1.0 sec

内存限制: 256 MB

Hazy moonlight poors on $n\times m$ ponds,which are lined up as a matrix with $n$ rows and $m$ columns.

The pond located at the $i$-th row and the $j$-th column contains $a_{i,j}$ lotus flowers (where $1\le i\le n,1\le j\le m$).

Now,the Plovery Frog plans to choose a sub-matrix,and then merge all of the ponds in it. And he hopes that the huge merged ponds will contains exactly $k$ lotus flowers.

So,the Plovery Frog wants to know that,how many different ways choosing the sub-matrix can meets his requirement.

In other words,

he wants to know the number of tuples in format $(l_1,r_1,l_2,r_2),\ 1\le l_1\le r_1\le n,1\le l_2\le r_2\le m $ ,which makes below constraint satisfied:
$$
\bigg(\sum_{i=l_1}^{r_1}\sum_{j=l_2}^{r_2}a_{i,j} \bigg)= k
$$

输入格式

The first line contains an integer $T\ (1\le T)$ denoting the number of test cases.

There are $T$ test cases, for each one:

The first line contains $2$ integers $n,m\ (1\le n,m \le 10^5)$ ,denoting the number of the rows and columns in the matrix.

For the next $n$ lines, each line contains $m$ integers,the integer located at the $i$-th line and the $j$-th column is $a_{i,j}\ (0\le a_{i,j}\le 10^9)$.

The next line contains an integer, $k\ (0\le k\le 10^{14})$ , denoting the required sum of the elements in the sub-matrix.

For all of the $T$ test cases,$\sum n\times m \le 2\times10^5$ is satisfied.

输出格式

For each test case, output a line, which contains an integer as your answer.

样例

Input
2
2 2
1 9
0 5
1
5 5
3 1 4 1 5
9 2 6 5 3
5 3 8 4 6
2 6 4 3 3
8 3 2 7 9
19
Output
2
7