Minimum Sensors Coverage

You are given a grid of size M × N where some cells contain sensors (denoted by 1) and others are empty (denoted by 0). A sensor placed in cell \((i, j)\) can monitor all cells within a Manhattan distance \(D\). The Manhattan distance between cell \((i, j)\) and cell \((x, y)\) is given by \(|x-i| + |y-j|\).

Your task is to determine whether the existing sensors cover the entire grid. If every cell in the grid is within the monitoring range of at least one sensor, output the number of sensors currently deployed; otherwise, output \(-1\).

Note: The sensors are already placed in the grid and you are not allowed to reposition or add sensors. You merely have to verify full coverage.

inputFormat

The input begins with an integer \(T\) representing the number of test cases. Each test case is formatted as follows:

• The first line contains two integers, \(M\) and \(N\), which are the number of rows and columns of the grid.
• The next \(M\) lines each contain \(N\) space-separated integers (either 0 or 1) representing the grid.
• The last line of the test case contains an integer \(D\) representing the sensor's monitoring range.

outputFormat

For each test case, output a single line containing the number of sensors if the grid is fully covered; otherwise, output \(-1\).

## sample

4
3 3
1 0 0
0 0 0
0 0 1
2
4 4
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 1
1
2 2
0 0
0 0
1
3 3
1 1 1
1 1 1
1 1 1
1

2
-1
-1
9

</p>