맨해튼의 핫도그 가판대

두 친구 버락과 미트는 각자 맨해튼에 핫도그 가판대를 하나씩 열려고 하며, 가장 좋은 두 위치를 찾고 있다.

두 사람 모두 노출을 극대화하기 위해 가판대를 교차로에 두고 싶어 한다. 맨해튼에는 이미 많은 가판대가 있으며 모두 교차로에 있다. 다른 가판대(상대방이 새로 세우는 가판대 포함)와 가까우면 손님이 줄어들기 때문에, 두 사람은 자신의 가판대를 다른 모든 가판대로부터 가능한 한 멀리 두고 싶어 한다.

맨해튼을 세로 도로 $w$개와 가로 도로 $h$개로 이루어진 유한한 격자로 생각하자. 세로 도로는 $x = 0, 1, \dots, w-1$에, 가로 도로는 $y = 0, 1, \dots, h-1$에 있다. 이웃한 평행 도로 사이의 간격은 모두 $1$이므로, 두 교차로 $(x_1, y_1)$과 $(x_2, y_2)$ 사이의 거리는 $|x_1 - x_2| + |y_1 - y_2|$이다.

어떤 교차로의 프라이버시는 그 교차로에서 다른 모든 가판대까지의 거리 중 최솟값이다. 두 개의 새 가판대를 놓고 나면 각 새 가판대도 상대방에게는 하나의 가판대가 되므로, 버락 위치의 프라이버시는 미트 위치까지의 거리에, 미트 위치의 프라이버시는 버락 위치까지의 거리에 영향을 받는다. 버락과 미트는 두 프라이버시 중 더 작은 값이 최대가 되도록 두 교차로를 고르려 한다. 그 최댓값을 출력하라.

첫 줄에는 테스트 케이스의 수를 나타내는 양의 정수 하나가 주어진다(최대 $100$). 각 테스트 케이스는 다음과 같다.

• 세 정수 $n$, $w$, $h$가 공백으로 구분되어 한 줄에 주어진다($0 \le n \le 1000$, $2 \le w, h \le 1000$). 각각 기존 가판대의 수, 세로 도로의 수, 가로 도로의 수이다.
• 이어서 $n$개의 줄에 각각 두 정수 $x_i$, $y_i$가 공백으로 구분되어 주어진다($0 \le x_i < w$, $0 \le y_i < h$). $i$번째 기존 가판대가 있는 교차로이다.

모든 기존 가판대는 서로 다른 교차로에 있으며, 가판대가 없는 교차로가 적어도 두 개 있다.

각 테스트 케이스마다 한 줄에 정수 하나를 출력한다. 버락과 미트가 동시에 얻을 수 있는 프라이버시의 최댓값이다.

첫 번째 테스트 케이스에서는 $4 \times 4$ 격자에 기존 가판대가 $(0, 1)$ 한 곳에 있다. 새 가판대 두 개를 $(2, 3)$과 $(3, 0)$에 놓으면 각각의 프라이버시가 $4$가 된다. 두 위치 모두 기존 가판대로부터 거리가 $4$ 이상이고, 두 위치 사이의 거리도 $4$이기 때문이다. 이보다 더 좋은 배치는 없으므로 답은 $4$이다.

기존 가판대가 하나도 없으면 두 새 가판대를 서로 마주 보는 두 꼭짓점에 놓을 수 있으므로 답은 $(w-1) + (h-1)$이다.