세 네모

벽지에는 한 변이 1cm인 정사각형 무늬가 격자처럼 그려져 있다. 벽에 앉은 파리는 이 무늬의 격자점에만 앉았고, 철승이는 파리가 앉았던 자리마다 점을 하나씩 찍어 두었다. 격자점의 위치는 정수 좌표 $(x, y)$로 나타낸다.

이제 벽지와 무늬가 같은 정사각형 종이 3장으로 점을 모두 가리려고 한다. 세 장은 크기가 모두 같아야 하고, 한 변의 길이는 정수 cm여야 한다. 종이는 무늬의 격자선에 딱 맞춰 붙이므로 종이의 네 변은 정수 좌표 위에 놓인다. 종이끼리 겹쳐도 되고, 점을 하나만 가리거나 하나도 가리지 못하는 종이가 있어도 된다. 한 변의 길이가 0인 종이도 쓸 수 있으며, 이 종이는 격자점 하나만 가린다. 점이 종이의 변이나 꼭짓점 위에 놓이면 가려진 것으로 본다.

한 변의 길이가 $s$인 종이를 격자점 $(a, b)$에 놓으면 $a \le x \le a+s$이고 $b \le y \le b+s$인 점 $(x, y)$를 모두 가린다. 점을 모두 가릴 수 있는 $s$의 최솟값을 구하는 프로그램을 작성하시오.

첫 줄에 테스트 케이스의 수 $T$가 주어진다.

각 테스트 케이스의 첫 줄에는 점의 개수 $n$ ($1 \le n \le 100\,000$)이 주어진다. 이어지는 $n$개의 줄에는 점의 좌표 $x_i$와 $y_i$ ($-1\,000\,000\,000 \le x_i, y_i \le 1\,000\,000\,000$)가 공백을 사이에 두고 주어진다. 같은 좌표가 여러 번 나올 수 있다.

각 테스트 케이스마다 종이 한 변의 최소 길이를 정수로 한 줄에 출력한다. 이 값은 0이 될 수 있다.