캥거루 우리

농부이자 사육사로 잘 알려진 유제프 씨는 늘 농장을 키울 방법을 찾습니다. 이번에는 캥거루를 기르기로 했습니다.

유제프 씨는 $1 \times 1$ 크기의 정사각형 밭들을 규칙적인 격자로 나눈 목초지를 준비했습니다. 목초지는 각 줄에 $K$개씩 밭이 놓인 줄이 $W$개 있어, 밭이 모두 $W \times K$개입니다.

목초지에는 $N$마리의 캥거루가 있고, 각 캥거루는 서로 다른 밭 하나를 자기가 좋아하는 밭으로 골랐습니다. 유제프 씨는 모든 캥거루가 좋아하는 밭을 전부 담으면서도 가능한 한 작은 우리를 세우려고 합니다.

우리는 다음 조건을 만족해야 합니다.

• 볼록 다각형이어야 하며, 그 경계는 서로 이웃한 밭들의 중심을 차례로 잇는 선분들로 이루어집니다. 두 밭은 변 또는 꼭짓점을 공유하면 이웃한 것으로 봅니다. (달리 말하면 다각형의 각 변은 가로, 세로, 또는 45도 대각선 방향입니다.)
• 모든 캥거루가 좋아하는 밭을 담아야 합니다. 어떤 밭은 우리의 경계가 그 밭의 중심을 지나거나 그 밭의 중심이 우리 내부에 있을 때 담긴 것으로 봅니다.

이 조건들을 만족하는 우리 중에서, 담고 있는 밭의 수가 가장 적어야 합니다.

최적의 우리가 담는 밭의 수를 구하는 프로그램을 작성하세요.

첫째 줄에 테스트 세트의 수 $Z$ ($1 \le Z \le 10$)가 주어집니다. 이어서 $Z$개의 세트가 주어집니다.

각 세트의 첫째 줄에는 공백으로 구분된 세 정수 $W$, $K$, $N$ ($1 \le W, K \le 10^6$, $3 \le N \le 10^6$)이 주어지며, 각각 목초지의 크기와 캥거루의 수를 뜻합니다.

이어지는 $N$개의 줄에는 각 캥거루가 좋아하는 밭의 좌표가 공백으로 구분된 두 정수 $w_i$, $k_i$ ($1 \le w_i \le W$, $1 \le k_i \le K$)로 주어집니다. 여기서 $w_i$는 줄 번호(행), $k_i$는 칸 번호(열)입니다. 모든 좋아하는 밭은 서로 다릅니다.

모든 테스트 세트는 최적의 우리를 이루는 다각형의 넓이가 0이 아닌 비퇴화 경우만을 다룹니다.

각 테스트 세트마다 최적의 우리가 담는 밭의 수를 한 줄에 하나씩 출력하세요.