우리 학교는 다른 학교가 부러워하는 도서실을 가지고 있다. 장서를 다량 보유하고 있을 뿐 아니라 전자도서를 볼 수 있는 컴퓨터도 여러 대 설치되어 있고, 바닥에는 카펫이 깔려있다. 최근 도서실의 가구배치를 새로 하게 되었는데, 가구가 놓여있던 자리에는 얼룩이 져서 아주 보기가 흉하였다. 그래서 3 x 3 크기의 카펫 여러 장으로 얼룩진 부분을 모두 가리기로 하였다.

도서실 바닥에는 1 x 1 타일이 m행 n열 격자 형태로 놓여있고 이 중에서 c개의 타일에 얼룩이 졌다. 카펫을 놓을 때는 카펫의 변이 도서실의 벽과 평행하도록 놓아야 하며 정확히 9개의 타일이 가려지게 놓아야 한다.

예를 들어, 다음 그림과 같이 6 x 11 크기의 도서실의 (4, 3), (6, 5), (3, 6)과 (4, 7) 위치에 얼룩이 있다고 하자. 모든 얼룩을 가리기 위해서는 아래 그림과 같이 최소 2개의 카펫을 배치하여야 한다.

모든 얼룩을 가리기 위하여 배치해야 할 최소 카펫의 수를 구하는 프로그램을 작성하시오.​ 

입력은 여러 개의 테스트케이스로 구성되어 있다. 첫 번째 줄에는 테스트 케이스의 수 t가 주어진다. (1 ≤ t ≤ 5)

각 테스트케이스의 첫 줄에는 도서실의 크기를 나타내는 두 자연수 m과 n이 주어진다. (3 ≤ m ≤ 10, 3 ≤ n ≤ 1,000).

둘째 줄에는 얼룩의 개수를 나타내는 정수 c가 주어진다. (0 ≤ c ≤ mn) 그리고 다음 c개의 줄에 각 얼룩의 좌표가 주어진다.

얼룩의 좌표는 서로 다르게 주어지며, 모두 도서실 안에 위치한다.​ 

각 테스트케이스 별로 얼룩을 모두 가리기 위해 필요한 카펫의 최소 개수를 의미하는 하나의 정수를 출력한다.