yet another mst problem

좌표평면 위에 서로 다른 $N$개의 정수점이 주어진다. 두 점 $(x_1,y_1)$과 $(x_2,y_2)$ 사이의 거리는 맨해튼 거리 $|x_1-x_2|+|y_1-y_2|$이다.

주어진 점 가운데 정확히 하나를 골라 원하는 정수점으로 옮길 수 있다. 옮긴 뒤의 $N$개 점을 정점으로 하는 최소 스패닝 트리의 가중치 합을 가능한 한 작게 만들려고 한다.

가능한 최소 가중치 합을 구하여라. 고른 점을 원래 위치로 옮기거나 다른 점과 같은 좌표로 옮겨도 된다.

입력은 다음과 같은 형식으로 주어진다.

$T$ case$_1$ case$_2$ $\vdots$ case$_T$

각 케이스는 다음과 같은 형식으로 주어진다.

$N$ $x_1\ y_1$ $x_2\ y_2$ $\vdots$ $x_N\ y_N$

각 테스트 케이스마다 가능한 최소 맨해튼 MST 가중치 합을 한 줄에 출력한다.

• $1 \leq T \leq 70$.
• $1 \leq N \leq 70$.
• $1 \leq x_i,y_i \leq 10^9$ ($1 \leq i \leq N$).
• $(x_i,y_i) \neq (x_j,y_j)$ ($1 \leq i < j \leq N$).
• 모든 테스트 케이스에 대한 $N$의 합은 $70$ 이하이다.