你生活在一个无限平面上,上面有笛卡尔坐标系。您可以一次移动到四个相邻点(左、右、上、下)中的任何一个。
更正式地说,如果您站在 $$$(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)$$$$$$
在第三个测试用例中,我们可以在不进行任何移动的情况下收集所有盒子。