题目描述

给定一个长度为 $2n$ 的整数序列 $a$。你需要将这 $2n$ 个整数分成 $n$ 对，每一对代表平面上的一个点的坐标。序列 $a$ 中的每个数都必须恰好作为一个点的 $x$ 或 $y$ 坐标。注意，有些点可以相同。

在形成这些点之后，你需要选择一条路径 $s$，该路径从这些点中的某一个出发，终止于某一个点，并且至少访问所有 $n$ 个点一次。

路径 $s$ 的长度定义为路径上所有相邻点之间距离之和。这里，两个点 $(x_1, y_1)$ 和 $(x_2, y_2)$ 之间的距离定义为 $|x_1-x_2| + |y_1-y_2|$。

你的任务是，合理地组成 $n$ 个点，并选择一条路径 $s$，使得路径 $s$ 的长度最小。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 100$），表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 100$），表示需要组成的点的数量。

接下来一行包含 $2n$ 个整数 $a_1, a_2, \dots, a_{2n}$（$0 \le a_i \le 1000$），表示序列 $a$。

输出格式

对于每个测试用例，第一行输出路径 $s$ 的最小可能长度。

接下来的 $n$ 行中，第 $i$ 行输出两个整数 $x_i$ 和 $y_i$，表示第 $i$ 个需要访问的点的坐标。

如果有多组答案，输出任意一组均可。

说明/提示

例如，在第一个测试用例中，你可以组成点 $(10, 1)$ 和 $(15, 5)$，并从第一个点出发到第二个点。此时路径长度为 $|10 - 15| + |1 - 5| = 5 + 4 = 9$。

在第二个测试用例中，你可以组成点 $(20, 20)$、$(10, 30)$ 和 $(10, 30)$，并按这个顺序访问它们。此时路径长度为 $|20 - 10| + |20 - 30| + |10 - 10| + |30 - 30| = 10 + 10 + 0 + 0 = 20$。

由 ChatGPT 4.1 翻译

样例

2
2
15 1 10 5
3
10 30 20 20 30 10

9
10 1
15 5
20
20 20
10 30
10 30