Rectilinear Polygon

You are given $n$ points with integer coordinates in the plane. Determine whether it is possible to build a simple rectilinear polygon whose vertices are exactly these points.

A rectilinear polygon satisfies all of the following:

• It has at least $4$ vertices.
• Every edge is either horizontal or vertical.
• Each vertex is an endpoint of exactly one horizontal edge and exactly one vertical edge.
• It is simple: no two edges cross, other than adjacent edges meeting at a shared endpoint, and the polygon has no holes.

Every given point must be used as a vertex. If such a polygon exists, output its perimeter (the sum of the lengths of all edges); otherwise output $-1$.

The first line contains an integer, the number of test cases.

Each test case begins with an integer $n$ ($4 \le n \le 100000$), the number of points, followed by $n$ pairs of integers giving the $x$ and $y$ coordinates of the points.

For each test case output a single line. If a valid rectilinear polygon through the given points exists, output its perimeter as an integer; otherwise output $-1$.