매트리스 얼룩 지우기

추석 연휴에 홍준이는 집에서 파티를 열었다. 어린 아이가 많이 왔고, 다음 날 홍준이는 침대 시트 밑 매트리스에 얼룩이 여러 개 스며든 것을 발견했다. 매트리스를 전부 세탁하는 비용이 너무 비싸서 홍준이는 작은 얼룩 제거 도구를 사려고 한다.

매트리스의 윗면은 $m$행 $n$열의 직사각형 격자다. 왼쪽 위 칸의 좌표는 $(1, 1)$이고 오른쪽 아래 칸의 좌표는 $(m, n)$이다. 좌표 $(r, s)$는 위에서 $r$번째 행, 왼쪽에서 $s$번째 열에 있는 칸을 뜻한다. 얼룩 하나는 칸 하나를 덮는다.

얼룩 제거 도구는 매트리스 안에 완전히 들어가는 $3 \times 3$ 칸 영역을 골라 그 영역의 얼룩을 한 번에 모두 지운다. 영역의 변은 매트리스의 변과 평행하다. 도구는 한 번 쓰면 버리는 소모품이라서 도구 하나가 처리하는 영역도 하나다. 매트리스의 크기와 얼룩의 위치가 주어질 때, 얼룩을 모두 지우는 데 필요한 도구의 최소 개수를 구하자.

크기가 $6 \times 11$인 매트리스에서 얼룩이 $(4, 3)$, $(6, 5)$, $(3, 6)$, $(4, 7)$에 있으면 도구 두 개로 충분하다. 4행부터 6행, 3열부터 5열까지의 영역이 $(4, 3)$과 $(6, 5)$를 지우고, 2행부터 4행, 5열부터 7열까지의 영역이 $(3, 6)$과 $(4, 7)$을 지운다.

첫 줄에 테스트케이스의 개수 $T$가 주어진다. 이어서 $T$개의 테스트케이스가 주어진다.

각 테스트케이스의 첫 줄에는 매트리스의 크기를 나타내는 두 자연수 $m$과 $n$이 주어진다. ($3 \le m \le 10$, $3 \le n \le 1000$) 둘째 줄에는 얼룩의 개수 $c$가 주어진다. ($0 \le c \le mn$) 다음 $c$개의 줄에는 얼룩 하나의 행 번호와 열 번호가 공백으로 구분되어 주어진다. 행 번호는 $1$ 이상 $m$ 이하, 열 번호는 $1$ 이상 $n$ 이하이고, 얼룩의 좌표는 모두 서로 다르다.

각 테스트케이스마다 얼룩을 모두 지우는 데 필요한 도구의 최소 개수를 한 줄에 출력한다.