Description

Given is n points with integer coordinates in the plane. Is it is possible to construct a (simple) rectilinear polygon with the given points as vertices? In a rectilinear polygon there are at least 4 vertices, and every edge is either horizontal or vertical. Each vertex is an endpoint of exactly one horizontal edge and one vertical edge. There are no holes in a polygon. For example:

You are guaranteed that, if there is a rectilinear polygon (or a set of rectilinear polygons) that is a solution to a test case as described above, then it is, in fact, just a single rectilinear polygon, and that rectilinear polygon is simple (that is, it has no intersecting edges).

Input

The first line of input is an integer giving the number of cases that follow. There is at least one test case and at most 10,000 test cases. The input of each case starts with an integer 4 ≤ n ≤ 10,000, giving the number of points for this test case. This is followed by n pairs of integers specifying the x and y coordinates of the points for the case.

Output

The output should contain one line for each case on input. Each line should contain one integer number giving the length of the perimeter of the rectilinear polygon that passes throught the given points, when it exists; otherwise, it should contain -1.

Sample Input

1
8
1 2
1 0
2 1
2 2
3 2
3 1
4 0
4 2

Sample Output

12