Jack Edmonds 是一位美国计算机科学家。他可能最被 ACM-ICPC 社区所熟知的是作为 Edmonds-Karp 算法的共同发明者，该算法以 $O(|V||E|^2)$ 的复杂度解决了最大流问题。然而，他对该领域最重要的贡献或许是 Cobham-Edmonds 假设，它定义了多项式时间的概念，作为判断算法是否实用的方法。如今，我们认为 $P$（确定性多项式时间类）中的问题和 $NP$（非确定性多项式时间类）中的问题分别是可高效求解和可高效验证的。“$P$ 对 $NP$ 问题”旨在探讨 $P$ 是否等于 $NP$，这是计算机科学中主要的未解难题，也是七大千禧年大奖难题之一。大多数计算机科学家认为 $P \neq NP$，但他们仍无法提供正确性证明。另一方面，许多人试图通过证明某个 $NP$-hard 问题（至少与任何 $NP$ 问题一样难）属于 $P$ 来证明 $P = NP$，但他们都失败了。

一个著名的被称为旅行商问题的难题是 $NP$-hard 问题的一个例子。该问题描述如下：给定一系列目的地以及每对目的地之间的距离，从起点出发访问所有目的地并返回起点的最短可能路线是什么？现在，作为一名聪明的程序员，我相信你可以很快解决这个问题。但有一个问题。为了增加挑战性，我们不提供地图！相反，你将获得每个目的地的坐标，并且还没有修建任何道路。如果某些目的地没有连接到其他所有目的地，显然无法访问所有目的地。

假设有 $n$ 个目的地。它们的坐标为 $(x_1, y_1), \dots, (x_n, y_n)$，其中 $(x_1, y_1)$ 是起点。市长打算帮助你。他会为你修建道路。然而，他既愚蠢又懒惰。因为他很愚蠢，他只能通过水平和垂直线段直接连接两个目的地 $(x_i, y_i)$ 和 $(x_j, y_j)$。因此，其长度为 $|x_i - x_j| + |y_i - y_j|$。因为他很懒，他不会为你修建超过 $n - 1$ 条道路。他的顾问告诉他，$n - 1$ 条道路足以让你到达所有目的地。由你来决定修建哪些道路。你能告诉我访问每个目的地并返回起点的最短路线长度是多少吗？

输入格式

输入包含一个整数 $T(T \le 20)$，表示测试用例的数量。 接下来，每个测试用例的第一行包含一个整数 $n(n \le 10,000)$，表示目的地的数量。接下来的 $n$ 行包含两个整数 $x, y(-1,000 \le x, y \le 1,000)$，表示目的地的坐标。

输出格式

对于每个测试用例，输出访问每个目的地并返回起点的最短路线长度。

样例

样例输入 1

3
3
1 1
2 2
3 3
4
2 1
-1 2
-2 -1
1 -2
6
1 2
2 3
2 2
3 4
4 3
3 1

样例输出 1

8
24
16