Hot Dogs in Manhattan

Two friends, Barack and Mitt, each want to open a hot dog stand in Manhattan, and they are looking for the two best locations.

Both want to place their stand at an intersection for maximum exposure. Manhattan already has many existing stands, all located at intersections. A stand placed close to another stand (including the other friend's new stand) attracts fewer customers, so they want their stands to be as far as possible from every other stand.

Model Manhattan as a finite square grid of $w$ vertical streets and $h$ horizontal streets. Vertical streets are at $x = 0, 1, \dots, w-1$ and horizontal streets at $y = 0, 1, \dots, h-1$. Consecutive parallel streets are one unit apart, so the distance between intersections $(x_1, y_1)$ and $(x_2, y_2)$ is $|x_1 - x_2| + |y_1 - y_2|$.

The privacy of an intersection is the minimum distance from it to every other stand. Once both new stands are placed, each new stand also counts as a stand for the other, so the privacy of Barack's location depends on the distance to Mitt's location and vice versa. Barack and Mitt want to choose two intersections so that the smaller of their two privacies is as large as possible. Output that maximum value.

The first line contains one positive integer: the number of test cases, at most $100$. Each test case is given as follows:

• One line with three space-separated integers $n$, $w$, and $h$ ($0 \le n \le 1000$ and $2 \le w, h \le 1000$): the number of existing stands and the number of vertical and horizontal streets.
• $n$ lines, each with two space-separated integers $x_i$ and $y_i$ ($0 \le x_i < w$ and $0 \le y_i < h$): the intersection of the $i$-th existing stand.

All existing stands are at distinct intersections, and at least two intersections have no stand.

For each test case, output one line with a single integer: the maximum privacy that both Barack and Mitt can simultaneously achieve.

In the first test case there is one existing stand at $(0, 1)$ on a $4 \times 4$ grid. Placing the two new stands at $(2, 3)$ and $(3, 0)$ gives each a privacy of $4$: both are at distance at least $4$ from the existing stand, and they are at distance $4$ from each other. No placement does better, so the answer is $4$.

When there is no existing stand, the two new stands can be put at opposite corners, so the answer is simply $(w-1) + (h-1)$.