Bugs Integrated, Inc.

Bugs Integrated, Inc.는 고성능 메모리 칩을 만드는 대형 제조사입니다. 이 회사는 새로운 6테라바이트 Q-RAM 칩의 생산을 시작하려고 합니다. 각 칩은 $2 \times 3$ 직사각형 모양으로 배열된 6개의 단위 정사각형으로 이루어져 있습니다.

Q-RAM 칩은 다음과 같이 만들어집니다. 먼저 $N \times M$개의 단위 정사각형으로 나누어진 직사각형 실리콘 판을 준비합니다. 그런 다음 모든 칸을 꼼꼼히 검사하여 불량인 칸을 검은 펜으로 표시합니다.

마지막으로 실리콘 판을 잘라 메모리 칩을 만듭니다. 각 칩은 $2 \times 3$ 또는 $3 \times 2$ 크기의 단위 정사각형으로 이루어지며, 어떤 칩도 불량(표시된) 칸을 포함해서는 안 됩니다. 모든 정상 칸이 반드시 어떤 칩에 포함되도록 자를 수 있는 것은 아닙니다. 회사는 버리는 정상 칸을 최대한 줄이고 싶어 하며, 따라서 만들 수 있는 칩의 개수가 최대가 되도록 판을 자르는 방법을 알고 싶어 합니다.

여러 실리콘 판의 크기와 각 판의 불량 칸 목록이 주어집니다. 각 판에 대해 잘라낼 수 있는 칩의 최대 개수를 계산하는 프로그램을 작성하세요.

첫째 줄에 실리콘 판의 개수를 나타내는 정수 $D$ ($1 \le D \le 5$)가 주어집니다. 이어서 각 실리콘 판을 설명하는 $D$개의 블록이 주어집니다.

각 블록의 첫째 줄에는 공백으로 구분된 세 정수 $N$ ($1 \le N \le 150$), $M$ ($1 \le M \le 10$), $K$ ($0 \le K \le N \cdot M$)가 주어집니다. $N$은 판의 길이, $M$은 판의 높이, $K$는 판에 있는 불량 칸의 개수입니다.

이어지는 $K$개의 줄에는 불량 칸의 목록이 주어집니다. 각 줄에는 하나의 불량 칸의 좌표를 나타내는 두 정수 $x$와 $y$ ($1 \le x \le N$, $1 \le y \le M$)가 주어집니다. 왼쪽 위 칸의 좌표는 $[1, 1]$이고, 오른쪽 아래 칸의 좌표는 $[N, M]$입니다.

각 실리콘 판에 대해 잘라낼 수 있는 메모리 칩의 최대 개수를 한 줄에 하나씩 출력합니다.

위 그림은 실리콘 판을 칩으로 잘라내는 예시를 보여 줍니다.