Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

K. Point Diameter
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Zoro has somehow gotten completely lost again, this time on a flat island with $$$n$$$ landmarks. Sanji is furious and tries to guide him using a map. The $$$i$$$-th landmark is at $$$(x_{i}, y_{i})$$$.

To make things easier for Zoro's terrible sense of direction, Sanji decides to erase up to two landmarks from the map. The "lost diameter" of the map is the biggest Manhattan distance between any two remaining landmarks.

The Manhattan distance between $$$(x_{1}, y_{1})$$$ and $$$(x_{2}, y_{2})$$$ is $$$|x_{1}-x_{2}| + |y_{1}-y_{2}|$$$. If less than two landmarks are left, the diameter is 0.

Find the smallest possible lost diameter Sanji can achieve after removing at most two landmarks.

Input

The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^{4}$$$) — the number of test cases.

The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 2 \times 10^{5}$$$) — the number of points.

Each of the next $$$n$$$ lines contains two integers $$$x_{i}$$$ and $$$y_{i}$$$ ($$$-10^{9} \le x_{i}, y_{i} \le 10^{9}$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \times 10^{5}$$$.

Output

For each test case, output one integer — the smallest possible diameter.

Example
Input
2
3
0 0
10 0
0 10
4
0 0
2 0
0 2
2 2
Output
0
2
Note

In the first test case, remove (10,0) and (0,10). Only one point remains, so the diameter is 0.

In the second test case, after removing two opposite corners, the remaining two points can have Manhattan distance 2.