Peaks

Time limit2sMemory limit256 MB

Summary

Count grid cells that stay locally maximal when reachability is restricted to cells within height d of the starting cell, for many test cases up to 500x500.

Level: Hard8 of 10
Topics: Union-find, Sorting, Graph
Solved: No attempts yet

Problem

Sang-geun works at a company that makes large maps. His current task is to find the peaks of mountains in a landscape.

You are given a grid map where each cell has a height. Consider a cell whose height is $h$ . Starting from this cell, you may move between orthogonally adjacent cells (up, down, left, right), but you are never allowed to step onto a cell whose height is $h-d$ or lower. If, under this restriction, it is impossible to reach any cell taller than $h$ , then the cell is called a $d$ -peak. In other words, a cell is a $d$ -peak if, using only cells with height greater than $h-d$ , you cannot walk to any cell higher than itself.

For example, a cell that is only slightly lower than a summit is not a peak if it connects directly to a higher summit without ever descending to low ground. Conversely, if reaching any higher cell forces you to pass through some sufficiently low cell (height $h-d$ or lower), then the cell is a $d$ -peak.

Given the height of every cell, write a program that counts how many cells are $d$ -peaks.

Input

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

The first line of each test case contains the map's number of rows $n$ , number of columns $m$ , and an integer $d$ ( $1 \le n, m \le 500$ , $1 \le d \le 10^9$ ). Each of the next $n$ lines contains $m$ integers, the heights $h$ of the cells ( $0 \le h \le 10^9$ ).

Output

For each test case, print the number of $d$ -peaks on its own line.

Examples7

Example 1

Input

1
6 10 2
0 0 0 0 0 0 0 0 0 0
0 1 2 1 1 1 1 0 1 0
0 2 1 2 1 3 1 0 0 0
0 1 2 1 3 3 1 1 0 0
0 2 1 2 1 1 1 0 2 0
0 0 0 0 0 0 0 0 0 0

Expected output

Example 2
Input
```
1
3 3 3
5 5 5
5 5 5
5 5 5
```
Expected output
```
9
```
Example 3
Input
```
1
1 1 1
7
```
Expected output
```
1
```
Example 4
Input
```
1
1 5 1
1 2 3 4 5
```
Expected output
```
1
```

Example 5

Input

2
2 2 1
1 1
1 1
2 2 1000000000
5 3
4 9

Expected output

4
1

Example 6
Input
```
1
3 3 1000000000
1 2 3
4 9 4
3 2 1
```
Expected output
```
1
```

Example 7

Input

2
2 3 1000000000
7 1 7
1 1 1
1 1 5
5

Expected output

2
1