지도 라벨러

지도 제작에서 지도를 만드는 일은 어려운 작업이며, 그중에서도 도시 이름을 자동으로 배치(라벨링)하는 것이 핵심적인 부분이다. 각 도시에는 그 위치에 텍스트 라벨을 붙여야 하고, 어떤 두 라벨도 서로 겹쳐서는 안 된다. 이 문제에서는 이 작업의 단순화된 형태를 다룬다.

각 도시는 평면 위의 한 점이라고 하자. 도시의 라벨은 변이 $x$축과 $y$축에 평행한 정사각형 안에 담기는 텍스트이다. 각 라벨은 도시의 점이 라벨의 위쪽 변 또는 아래쪽 변의 중점에 정확히 오도록 놓여야 한다. 올바른 라벨링에서는 모든 정사각형 라벨의 크기가 서로 같아야 하며, 어떤 두 라벨도 그 내부가 겹쳐서는 안 된다(단, 변끼리 맞닿는 것은 허용된다).

모든 도시의 좌표가 정수로 주어질 때, 올바른 라벨링이 존재하는 가장 큰 정수 라벨 크기를 구하여라.

첫째 줄에 테스트 케이스의 개수를 나타내는 정수 $t$ ($1 \le t \le 10$)가 주어진다. 각 테스트 케이스의 첫 줄에는 도시의 개수를 나타내는 정수 $m$ ($3 \le m \le 100$)이 주어진다. 이어지는 $m$개의 줄에는 각각 두 정수 $X$와 $Y$ ($-10000 \le X, Y \le 10000$)가 주어지며, 이는 한 도시의 $x$좌표와 $y$좌표이다. 좌표가 완전히 같은 두 도시는 존재하지 않는다.

각 테스트 케이스마다 올바른 라벨링이 가능한 최대 정수 라벨 크기를 한 줄에 출력한다.