← 返回题目列表

Codeforces · 1713/A

A. 旅行商问题

中文机器翻译题面 查看原题

你生活在一个无限平面上,上面有笛卡尔坐标系。您可以一次移动到四个相邻点(左、右、上、下)中的任何一个。

更正式地说,如果您站在 $$$(x, y)$$$ 点,您可以:

- 向左移动,移动到 $$$(x - 1, y)$$$,或者
- 向右走,移动到$$$(x + 1, y)$$$,或者
- 向上,移动到 $$$(x, y + 1)$$$,或者
- 向下移动到 $$$(x, y - 1)$$$。

这架飞机上有 $$$n$$$ 个盒子。第 $$$i$$$ 个框的坐标为 $$$(x_i,y_i)$$$。保证框位于 $$$x$$$ 轴或 $$$y$$$ 轴上。也就是说,$$$x_i=0$$$ 或 $$$y_i=0$$$。

如果你和盒子在同一点,你就可以收集一个盒子。如果您必须在 $$$(0,0)$$$ 点开始和结束,请求出收集所有这些盒子所需执行的最少移动次数。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 100$$$) — 盒子的数量。

以下 $$$n$$$ 行中的第 $$$i$$$ 行包含两个整数 $$$x_i$$$ 和 $$$y_i$$$ ($$$-100 \le x_i, y_i \le 100$$$) — 第 $$$i$$$ 框的坐标。保证 $$$x_i=0$$$ 或 $$$y_i=0$$$。

请注意,所有测试用例的 $$$n$$$ 之和没有上限。

输出

对于每个测试用例,输出一个整数 - 所需的最小移动次数。

示例

输入 #1

3
4
0 -2
1 0
-1 0
0 2
3
0 2
-3 0
0 -1
1
0 0

输出 #1

12
12
0

注意

在第一个测试用例中,使用所需最少移动次数的可能移动序列如下所示。

$$$$$$(0,0) \to (1,0) \to (1,1) \to (1, 2) \to (0,2) \to (-1,2) \to (-1,1) \to (-1,0) \to (-1,-1) \to (-1,-2) \to (0,-2) \to (0,-1) \to (0,0)$$$$$$

在第二个测试用例中,使用所需最少移动次数的可能移动序列如下所示。

$$$$$$(0,0) \to (0,1) \to (0,2) \to (-1, 2) \to (-2,2) \to (-3,2) \to (-3,1) \to (-3,0) \to (-3,-1) \to (-2,-1) \to (-1,-1) \to (0,-1) \to (0,0)$$$$$$

在第三个测试用例中,我们可以在不进行任何移动的情况下收集所有盒子。