G. Minimum Enclosing Axis-Parallel Square
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given $$$n$$$ points on a plane. The coordinates of the $$$i$$$-th point are $$$(x_i, y_i)$$$.

Print the minimum possible area of a square whose sides are parallel to the $$$x$$$ and $$$y$$$ axis, and cover all of the points.

Input

The input data contains several test cases. The first line contains one integer $$$t$$$ $$$(1 \le t \le 10^5)$$$ — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ $$$(1 \le n \le 2 \cdot 10^5)$$$ — the number of points.

Then $$$n$$$ lines follow, each line containing two integers $$$x_i$$$ and $$$y_i$$$ $$$(|x_i|, |y_i| \le 10^9)$$$ — the coordinates of $$$i$$$-th point.

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

Output

For each test case, print a single integer — the minimum possible area of the square.

Example
Input
2
4
1 0
-1 0
0 1
0 -1
3
2 0
-2 0
0 2
Output
4
16