There are N cities in a country. The cities are specified by the Cartesian coordinates. Each city is located at a point that contains integer coordinates. You are required to create a boundary that encloses all the cities. The boundary must be in the shape of a square and parallel to the coordinate axes.
Your task is to determine the minimum area that is enclosed by the created boundary such that cities are located on or inside the boundary.
Input format
Output format
For each test case, print a single non-negative integer denoting the minimum area of the square boundary that encloses all the cities inside or on its boundary.
Constraints
1≤T≤5
1≤N≤105
−109≤xi,yi≤109
In the first test case, all the points are on the boundary of a square of side 2. Hence answer=4.
In the second test case, the smallest square can be drawn is of side 2 having center at (0,0).