Problem #4901 - ECNU Online Judge

单点时限: 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 \leq i \leq n, 1 \leq j \leq 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 \leq l_{1} \leq r_{1} \leq n, 1 \leq l_{2} \leq r_{2} \leq m$ ，which makes below constraint satisfied：
$(\sum_{i = l_{1}}^{r_{1}} \sum_{j = l_{2}}^{r_{2}} a_{i, j}) = k$

输入格式

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

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

The first line contains $2$ integers $n, m (1 \leq n, m \leq 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 \leq a_{i, j} \leq 10^{9})$ .

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

For all of the $T$ test cases， $\sum n \times m \leq 2 \times 10^{5}$ is satisfied.

输出格式

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

样例

Input

Output

2
7

58 人解决，127 人已尝试。

66 份提交通过，共有 1067 份提交。

5.7 EMB 奖励。

创建: 2 年，6 月前.

修改: 2 年，6 月前.

最后提交: 2 年，1 月前.

来源: N/A

4901. Moonlight over the Lotus Pond

输入格式

输出格式

样例

服务

开源

关于我们