자연 친화적 마을

$R \times C$ 크기의 마을이 있다. 마을의 각 칸은 주택 또는 공터이다.

시장은 공터에 나무를 심어 마을을 자연 친화적으로 만들려고 한다. 주택과 변 또는 꼭짓점을 공유하는 최대 $8$개의 칸을 그 주택의 주변 칸이라고 하자.

나무를 심은 뒤 다음 두 조건을 만족해야 한다.

• 각 공터에는 나무를 최대 한 그루만 심을 수 있다.
• 모든 주택에 대해, 그 주택의 주변 칸에 심긴 나무의 수를 각각 구했을 때 그 값들의 총합이 $K$ 이상이어야 한다.

나무 한 그루를 심는 데에는 많은 비용이 든다. 조건을 만족하기 위해 심어야 하는 나무의 최소 개수를 구하여라.

입력은 다음과 같은 형식으로 주어진다.

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

각 테스트 케이스마다 조건을 만족하기 위해 심어야 하는 나무의 최소 개수를 한 줄에 출력한다. 조건을 만족하도록 나무를 심는 것이 불가능하다면 -1을 출력한다.

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