Problem H
Hot Dogs in Manhattan

The two friends Barack and Mitt have both decided to set up their own hot dog stand in Manhattan. They wish to find the two optimal locations for their stands.

First of all, they both want to put their stand at an intersection, since that gives them maximum exposure. Also, this being Manhattan, there are already quite a few stands in the city, also at intersections. If they put up a stand close to another (or each other’s) stand, they might not get that many customers. They would therefore like to put their stands as far from other stands as possible.

We model Manhattan as a finite square grid, consisting of $w$ vertical streets and $h$ horizontal streets. The vertical streets run from $x=0$ to $x=w-1$, while horizontal streets run from $y=0$ to $y=h-1$. All pairs of consecutive parallel streets are separated by the same distance, which we set as the unit distance. The distance between two intersections $(x_1, y_1)$ and $(x_2, y_2)$ is then given by $|x_1 - x_2| + |y_1 - y_2|$.

We indicate an intersection’s suitability by its privacy, which is the minimum of all distances from this intersection to all other hot dog stands. Barack and Mitt would like to find two intersections with the maximum amount of privacy, i.e. such that the smallest of the two privacies is as large as possible. Note that the privacy of Barack’s location can be determined by the distance to Mitt’s location and vice versa.

Input

On the first line one positive number: the number of test cases, at most 100. After that per test case:

• one line with three space-separated integers $n$, $w$ and $h$ ($0 \leq n \leq 1\, 000$ and $2 \leq w, h \leq 1\, 000$): the number of hot dog stands already in place and the number of vertical and horizontal streets, respectively.

• $n$ lines, each with two space-separated integers $x_ i$ and $y_ i$ ($0 \leq x_ i < w$ and $0 \leq y_ i < h$): the intersection where the $i$-th hot dog stand is located.

All hot dog stands are at different intersections. At least two intersections do not contain a stand.

Output

Per test case:

• one line with one integer: the maximum privacy that Barack and Mitt can both obtain.

3
1 4 4
0 1
6 6 6
0 0
1 1
2 2
3 3
4 4
5 5
2 8 3
0 0
7 0

4
5
3