25798번 - 초콜릿과 친구들의 습격

문제

코코의 초콜릿 기계는 가로와 세로가 4의 배수인 직사각형 모양의 초콜릿을 생산한다. 코코는 이 기계에서 생산된 $M \times N$ 크기의 초콜릿을 1ドル \times 2$ 또는 2ドル \times 1$ 크기로 나누어 판매하려고 한다. 하지만 어느 날 코코의 친구 $K$(0ドル \le K \le 4$)명이 놀러 와서 1ドル \times 1$ 초콜릿 한 칸씩을 떼어 먹어 버렸다. 남은 초콜릿을 나누었을 때 최대 몇 개의 초콜릿을 얻을 수 있는지 코코에게 알려주자.

입력

첫 줄에는 테스트 케이스의 개수 $T$가 주어진다. 그 다음 줄부터 $T$개의 테스트 케이스가 순서대로 주어진다.

각 테스트 케이스의 첫 줄에는 $M,ドル $N,ドル $K$의 값이 주어진다. $M$은 초콜릿의 가로의 길이, $N$은 세로의 길이이다. 다음 $K$줄에는 각각의 친구가 떼어 먹은 초콜릿 조각의 위치가 가로 좌표 $m,ドル 세로 좌표 $n$ 순으로 주어진다. 맨 왼쪽 위 칸의 좌표는 $(1, 1)$이며, 초콜릿 조각의 위치는 중복되지 않는다.

출력

각 테스트 케이스에 대해, 주어진 초콜릿을 나누어 얻을 수 있는 1ドル \times 2$ 또는 2ドル \times 1$ 초콜릿의 개수의 최댓값을 한 줄에 출력한다.

제한

• 1ドル \le T \le 1000$
• 4ドル \le M, N \le 1000$
• $M,ドル $N$은 4ドル$의 배수
• 0ドル \le K \le 4$
• 1ドル \le m \le M,ドル 1ドル \le n \le N$

힌트