Protect the Cities

There are N cities in Imaginary Land. The President of Imaginary Land uses the Cartesian coordinates. Each city is located at some point with integer coordinates. The President is very careful and concerned about the well-being of the citizens of his country.

For that reason, he wants to create a boundary and cover all the cities inside that boundary. The boundary should have the shape of a square and be parallel to the coordinate axes. Find the minimum area enclosed by the boundary such that all the cities are on or inside the boundary.

Input Specification

The first line of the input contains T, denoting the number of test cases (1 ≤ T ≤ 5). Each test case begins with a single positive integer N, denoting the number of cities in Imaginary Land (1 ≤ N ≤ 10⁵). Each of the next N lines contains two integers x_i and y_i, denoting the coordinates of the ith city (–10⁹ ≤ x_i, y_i ≤ 10⁹).

Output Specification

For each test case, output a single nonnegative integer, denoting the minimum area of the square boundary that encloses all the cities inside or on its boundary.

Sample Input

1. 2
2. 4
3. -1 -1
4. 1 1
5. 1 -1
6. -1 1
7. 3
8. 0 0
9. 1 1
10. 2 2

download as text file

Output for Sample Input

1. 4
2. 4

download as text file

Sample Explanation

In the first test case, all the points are on the boundary of a square of side 2. Hence the answer is 4.

In the second test case, the smallest square that can be drawn is of side 2, having its center at (1, 1).