#445 yet another mst problem

Statement

Statement language

There are $N$ distinct integer points on the coordinate plane. The distance between $(x_1,y_1)$ and $(x_2,y_2)$ is their Manhattan distance $|x_1-x_2|+|y_1-y_2|$ .

You must choose exactly one of the given points and move it to any integer point. After the move, consider a minimum spanning tree whose vertices are the resulting $N$ points.

Find the minimum possible total weight of this minimum spanning tree. You may move the chosen point to its original position or to the same coordinates as another point.

Input

The input is given from Standard Input in the following format:

$T$ case $_1$ case $_2$

Output

For each test case, print the minimum possible total weight of the Manhattan minimum spanning tree on one line.

Constraints

$1 \leq T \leq 70$ .
$1 \leq N \leq 70$ .
$1 \leq x_i,y_i \leq 10^9$ ().

Subtasks

#	Score	Constraints
1	25	$N \leq 8$ . The sum of $N$ over all test cases does not exceed $8$ .
2	75	No additional constraints.

Samples

Input

Output

2

Move the point at $(2,2)$ to $(2,1)$ . A spanning tree can then be formed with two edges of weight $1$ .