바닥 그림

박물관은 전시실 한 곳의 바닥에 정사각형 그림을 그리려고 한다. 전시실의 벽은 모두 직선이고, 이웃한 두 벽은 직각으로 만난다. 이웃하지 않은 두 벽은 서로 닿지 않으며 전시실 안에 기둥은 없다. 즉 바닥은 모든 변이 좌표축에 평행한 단순 다각형이다.

그림은 정사각형이고, 네 변이 벽과 평행해야 하며, 전체가 바닥 안에 들어가야 한다. 그림이 벽에 닿는 것은 허용한다. 그림을 가능한 한 크게 그리려고 한다. 변의 길이가 최대 얼마까지 가능한지 구하라.

첫 줄에 전시실의 개수 $T$가 주어진다 ($1 \le T \le 100$).

이어서 전시실마다 다음이 주어진다.

• 첫 줄에 꼭짓점의 개수 $n$ ($4 \le n \le 1000$)
• 다음 $n$개의 줄에 각 꼭짓점의 좌표 $x$와 $y$ ($0 \le x, y \le 100\,000$)가 공백으로 구분되어 주어진다

꼭짓점은 시계 방향으로 주어진다.

전시실마다 한 줄에 바닥에 들어가는 정사각형 그림의 최대 변의 길이를 정수 하나로 출력한다.