#714 Nature-Friendly Village

Statement

Statement language

There is a village represented by an $R \times C$ grid. Each cell is either a house or an empty lot.

The mayor wants to plant trees on empty lots. For a house, its neighboring cells are the at most $8$ cells that share an edge or a corner with it.

After planting trees, the following conditions must hold.

At most one tree may be planted on each empty lot.
For every house, count the trees planted in its neighboring cells. The sum of these counts over all houses must be at least $K$ .

Planting a tree is expensive. Find the minimum number of trees that must be planted to satisfy the conditions.

Input

The input is given from Standard Input in the following format:

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$

Output

For each test case, print the minimum number of trees that must be planted. If it is impossible to satisfy the conditions, print -1.

Constraints

$1 \le T \le 100\,000$ .
$1 \le R,C \le 1\,000$ .
.

Subtasks

#	Score	Constraints
1	30	$R,C \le 2$ . The sum of $R \times C$ over all test cases does not exceed $3\,000$ .

Samples

Input

3
1 1 0
.
2 3 2
.##
...
2 2 1
..
..

Output

0
1
-1

In the second test case, planting one tree in the middle cell of the second row places that tree next to both houses, so the total becomes $2$ .

In the third test case there are no houses, so the total remains $0$ regardless of where trees are planted.