벌집 연구

Albert는 취미로 벌집과 꿀벌에 대해 연구한다. 잘 알려져 있듯 벌집의 각 칸은 6각형 모양으로 생겼는데, 편의상 Albert가 연구하는 벌집의 크기는 $R$행 $C$열의 6각형 격자 모양이라 하자. 아래 그림은 $R = 5$, $C = 8$인 경우를 나타낸다.

Albert는 이 벌집의 빈칸 중 일부에 초소형 장치를 설치하여 꿀벌들의 행동을 관찰하고 싶어 한다. 하나의 장치는 6각형 벌집 한 칸을 차지하며, 한 칸에는 최대 한 개의 장치만 넣을 수 있다. 다만, 장치가 너무 가까이 있으면 서로 간섭현상이 일어날 수 있어 주의해야 한다. 구체적으로, 어떤 칸에 초소형 장치를 설치하면 인접한 (최대) 여섯 칸의 다른 칸 중 같은 열에 위치한 (최대) 두 개의 칸과는 간섭현상이 발생하지 않지만 다른 열에 위치한 (최대) 네 개의 칸과는 간섭현상이 발생한다.

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

• (1, 2)칸의 경우 인접한 칸이 총 다섯 개인데, 그중 (1, 2), (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 \gt 0$ 이라면 둘째 줄에는 $X$의 원소인 $K$개의 정수가 공백으로 구분되어 주어지고 셋째 줄에는 $Y$의 원소인 $K$개의 정수가 공백으로 구분되어 주어진다.

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

• 1 ≤ $T$ ≤ 5

• 1 ≤ $R, C$ ≤ 70

• 0 ≤ $K$ ≤ $\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)$ 는 고유하다 (중복된 좌표는 주어지지 않는다).