벌집 연구

Albert는 취미로 벌집과 꿀벌을 연구한다. 잘 알려진 대로 벌집의 각 칸은 육각형 모양이다. 편의상 Albert가 연구하는 벌집은 $R$행 $C$열의 육각형 격자로 본다. 아래 그림은 $R = 5$, $C = 8$인 경우이다.

Albert는 이 벌집의 빈칸 일부에 초소형 장치를 설치해 꿀벌의 행동을 관찰하려 한다. 장치는 칸 하나를 차지하며, 한 칸에는 장치를 최대 하나만 넣을 수 있다. 장치끼리 너무 가까우면 간섭이 일어날 수 있다. 구체적으로, 어떤 칸에 장치를 설치하면 인접한 최대 여섯 칸 중 같은 열의 최대 두 칸과는 간섭이 없지만, 다른 열의 최대 네 칸과는 간섭이 일어난다.

예를 들어 위 그림처럼 (1, 2), (2, 7), (5, 6) 칸에 장치를 설치했다고 하자.

• (1, 2)칸은 인접한 칸이 다섯 개이다. 그중 (1, 1), (2, 1), (1, 3), (2, 3) 네 칸은 간섭이 일어날 수 있어서 장치를 설치할 수 없다. (2, 2)는 (1, 2)칸과 인접하지만 간섭이 없다.
• (2, 7)칸은 인접한 칸이 여섯 개이다. 그중 (1, 6), (1, 8), (2, 6), (2, 8) 네 칸은 간섭이 일어날 수 있다. (1, 7)과 (3, 7)에는 장치를 추가로 설치할 수 있다.
• (5, 6)칸은 인접한 칸이 세 개이다. 그중 (5, 5), (5, 7) 두 칸은 간섭이 일어날 수 있다. (4, 6)에는 장치를 추가로 설치할 수 있다.

다른 제약 없이 간섭만 피하면서 장치를 최대한 많이 설치하려면 홀수 번째 열(1열, 3열, ...)에만 설치하면 된다. 이것이 최댓값이라는 사실은 Albert가 증명했다. 그러나 간섭 말고도 고려할 문제가 두 가지 있어서 Albert의 고민이 깊다.

첫째, 벌집의 모든 칸이 비어 있지는 않다. K개의 칸에는 유충 대신 고치가 있어서 장치를 설치할 수 없다. 고치가 있는 K개의 칸 중 i번째 칸의 위치를 $(X_i, Y_i)$로 나타낸다.

둘째, 같은 크기의 신형 센서도 설치해 테스트하고 싶다. 센서도 칸 하나를 차지하며, 고치가 있는 칸이나 다른 장치가 있는 칸에는 놓을 수 없다. 센서는 같은 열에 있는 다른 모든 장치와 간섭을 일으킨다. 다른 열의 칸은 인접하더라도 간섭을 일으키지 않는다. 신형 센서는 하나뿐이고, 반드시 설치해야 한다.

예를 들어 $R = 3$, $C = 3$, $K = 4$이고 $X = [1, 3, 1, 3]$, $Y = [1, 1, 2, 3]$인 격자판을 보자.

• 왼쪽에서 두 번째 그림: (2, 2) 칸에 신형 센서를 설치하고, (2, 1), (1, 3), (2, 3) 세 칸에 초소형 장치를 설치할 수 있다.
• 왼쪽에서 세 번째 그림: (2, 1) 칸에 신형 센서를 설치하고, (3, 2), (1, 3), (2, 3) 세 칸에 초소형 장치를 설치할 수 있다.
• 가장 오른쪽 그림: (2, 3) 칸에 신형 센서를 설치하고 (2, 2), (3, 2), (1, 3) 세 칸에 장치를 설치한 모습이다. 하지만 센서는 같은 열의 모든 장치와 간섭하므로 (1, 3) 칸의 장치와 간섭이 일어난다. 따라서 이 배치는 불가능하다. (2, 2) 칸의 장치는 센서와 열이 달라서 간섭이 없다.

이 예에서는 센서 외에 초소형 장치를 최대 3개 설치할 수 있다.

다른 예로 $R = 3$, $C = 4$, $K = 6$이고 $X = [2, 1, 3, 1, 3, 3]$, $Y = [1, 2, 2, 3, 3, 4]$인 격자판을 보자.

• 가운데 그림: 신형 센서를 (2, 2) 칸에 설치하고, (1, 1), (3, 1), (1, 4), (2, 4) 네 칸에 초소형 장치를 설치할 수 있다.
• 오른쪽 그림: 신형 센서를 (2, 3) 칸에 설치하고, (1, 1), (2, 2), (1, 4), (2, 4) 네 칸에 초소형 장치를 설치할 수 있다.

이 예에서는 센서 외에 초소형 장치를 최대 4개 설치할 수 있다. 이 두 방법 말고도 4개를 설치하는 방법이 있다.

$R$, $C$, $K$, $X$, $Y$가 주어질 때, 위 조건을 모두 만족하면서 설치할 수 있는 초소형 장치의 최대 개수를 구하라.

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

각 테스트 케이스의 첫 줄에는 $R$, $C$, $K$가 공백으로 구분되어 주어진다. $K = 0$이면 그 테스트 케이스의 입력은 이 줄에서 끝난다. $K > 0$이면 둘째 줄에 $X$의 원소인 $K$개의 정수가 공백으로 구분되어 주어지고, 셋째 줄에는 $Y$의 원소인 $K$개의 정수가 공백으로 구분되어 주어진다.

각 테스트 케이스의 정답을 한 줄에 하나씩 출력한다.

• $1 \le T \le 5$
• $1 \le R, C \le 70$
• $0 \le K \le \min(500, R\cdot C - 1)$
• $K > 0$인 테스트 케이스의 경우, $1 \le i \le K$인 모든 $i$에 대하여:
  • $1 \le X_i \le R$
  • $1 \le Y_i \le C$
  • 좌표 $(X_i, Y_i)$는 서로 다르다. 중복된 좌표는 주어지지 않는다.