/*
* main.cpp
*
* Created on: May 24, 2016
* Author: Radu Iacob
*/
#include <cstdio>
#include <algorithm>
#include <vector>
#include <limits>
#include <set>
#include <cstring>
#define NMAX 150020
#define MAX_T 12
#define MAX_N 150000
#define MAX_X 1000000000
class Point {
public:
int x, y;
int idx;
Point(int x, int y, int idx): x(x), y(y), idx(idx) {
}
void reflect_x() {
x = -x;
}
void reflect_y() {
y = -y;
}
void reflect_diagonal() {
std::swap(x, y);
}
bool operator<(const Point& other) const {
if (y == other.y) return x < other.x;
return other.y < y;
}
};
class Edge {
public:
int node1, node2;
int cost;
Edge(int node1, int node2, int cost)
: node1(std::min(node1, node2)),
node2(std::max(node1, node2)),
cost(cost)
{}
bool operator<(const Edge& other) const {
return cost < other.cost;
}
};
// Manhattan distance
inline int distance(Point& p1, Point& p2) {
return std::abs(p1.x - p2.x) + std::abs(p1.y - p2.y);
}
class AIB {
public:
std::vector<int> line;
std::vector<int> idx;
int size;
AIB(int size) : line(size + 1), idx(size + 1), size(size + 1) {}
void reset(int size) {
this->size = size;
std::fill(line.begin(), line.begin() + (size + 1), std::numeric_limits<int>::max());
std::fill(idx.begin(), idx.begin() + (size + 1), -1);
}
// position of the first 1 from the binary representation of 'it'
inline int zeros(int it) {
return (it ^ (it - 1)) & it;
}
// get the nearest neighbour, from the set of candidates [0 .. it]
inline int get(int it) {
int result_line = std::numeric_limits<int>::max();
int result_idx = -1;
for (; it > 0; it -= zeros(it)) {
// every point on the same line has the same distance
if (line[it] < result_line) {
result_line = line[it];
result_idx = idx[it];
}
}
return result_idx;
}
// update information about the nearest neighbour
inline void update(int it, Point& p, int p_idx) {
int p_line = p.y - p.x;
for(; it <= size; it += zeros(it)) {
if (line[it] > p_line) {
line[it] = p_line;
idx[it] = p_idx;
}
}
}
};
// priority tree, for fast access to the nearest point
AIB tree(NMAX);
void add_edges(std::vector<Point>& points,
std::vector<Edge>& edges,
std::vector<int>& active_lines) {
// sort points so that we traverse them in a zig-zag pattern
// from the upper-left corner
sort(points.begin(), points.end());
// an 'active set' of nearest-neighbour candidates only needs to
// account for the number of unique individual lines going north-west to south-east
for (unsigned int i = 0; i < active_lines.size(); ++i) {
active_lines[i] = points[i].x + points[i].y;
}
// sort and erase duplicate lines
std::sort(active_lines.begin(), active_lines.end());
active_lines.erase(std::unique(active_lines.begin(), active_lines.end()), active_lines.end());
tree.reset(active_lines.size());
for (unsigned int i = 0; i < points.size(); ++i) {
int line = std::lower_bound(active_lines.begin(),
active_lines.end(),
points[i].x + points[i].y) - active_lines.begin();
int nearest_neighbour = tree.get(line + 1);
if (nearest_neighbour != -1) {
edges.push_back(Edge(points[i].idx,
points[nearest_neighbour].idx,
distance(points[i], points[nearest_neighbour])));
}
tree.update(line + 1, points[i], i);
}
return;
}
void build_graph(std::vector<Point>& points,
std::vector<Edge>& edges) {
std::vector<int> active_lines(points.size(), 0);
// consider the octal partition of the 2d space:
// 1 2
// 0 3
// 7 4
// 6 5
// relative to each point, we try to compute the closest neighbour
// in section '0'. Next, we rotate the plan, so that we can apply
// the same reasoning for each section.
for (int x = 0; x < 2; ++x) {
for (int y = 0; y < 2; ++y) {
for (int diag = 0; diag < 2; ++diag) {
add_edges(points, edges, active_lines);
for (Point& p : points) { p.reflect_diagonal(); }
}
for (Point& p: points) { p.reflect_y(); }
}
for (Point& p: points) { p.reflect_x(); }
}
}
// disjoint sets data strctures
int dset[NMAX], rank[NMAX];
int find(int node) {
if (node != dset[node]) {
dset[node] = find(dset[node]);
}
return dset[node];
}
bool unite(int node1, int node2) {
int root1 = find(node1);
int root2 = find(node2);
if (root1 == root2) {
return false;
}
if (rank[root1] > rank[root2]) {
dset[root2] = root1;
rank[root1] += rank[root2];
} else {
dset[root1] = root2;
rank[root2] += rank[root1];
}
return true;
}
long long kruskal(std::vector<Point>& points,
std::vector<Edge>& edges) {
int N = points.size();
for (int i = 0; i < N; ++i) {
dset[i] = i;
rank[i] = 1;
}
long long mst_cost = 0;
std::sort(edges.begin(), edges.end());
int count_edges = 0;
for (auto it = edges.begin(); it != edges.end(); ++it) {
int node1 = it->node1;
int node2 = it->node2;
if (unite(node1, node2)) {
mst_cost += (long long)it->cost;
if (++count_edges == N - 1) {
return mst_cost;
}
}
}
return mst_cost;
}
int main () {
if (freopen("metrou4.in", "r", stdin) == NULL) {
fprintf(stderr, "Missing input file!\n");
return 1;
}
if (freopen("metrou4.out", "w", stdout) == NULL) {
fprintf(stderr,"Failure to open output file!\n");
return 1;
}
std::vector<Point> points;
std::vector<Edge> edges;
int T, ret;
ret = scanf("%d\n", &T);
if (ret != 1 || T < 1 || T > MAX_T) {
fprintf(stderr,"Invalid T %d\n", T);
return 1;
}
while (T--) {
int N;
ret = scanf("%d\n", &N);
if (ret != 1 || N < 1 || N > MAX_N) {
fprintf(stderr, "Invalid N %d\n", N);
return 1;
}
points.clear();
edges.clear();
for (int i = 0; i < N; ++i) {
int X, Y;
ret = scanf("%d%d\n", &X, &Y);
if (ret != 2 || X < 0 || X > MAX_X) {
fprintf(stderr,"Invalid point %d: %d %d\n", T, i, X);
return 1;
}
if (Y < 0 || Y > MAX_X) {
fprintf(stderr,"Invalid point %d: %d %d\n", T, i, Y);
return 1;
}
points.push_back(Point(X, Y, i));
}
build_graph(points, edges);
for (int i = 0; i < N; ++i) {
std::swap(points[i], points[points[i].idx]);
}
long long mst_cost = kruskal(points, edges);
printf("%lld\n", mst_cost);
}
return 0;
}