题目描述

Misaka Mikoto is the third-ranked Level 5 esper in $\textit{Academy City}$ and has been nicknamed $\textit{Railgun}$ due to her signature move. One day, several evil robots invade Academy City and Misaka is planning to terminate all of them.

Consider Academy City as a 2-dimensional plane. There are $n$ robots in total and the position of the $i$-th robot is $(x_i, y_i)$. Misaka will start moving from $(0, 0)$ and her railgun ability will terminate all robots sharing the same $x$- or $y$-coordinate with her. More formally, if Misaka is now located at $(x_m, y_m)$, all robots whose $x_i = x_m$ or $y_i = y_m$ will be terminated.

As Misaka hates decimals and Euclidean geometry, she will only move from one integer point to another integer point and can only move horizontally (parallel to the $x$-axis) or vertically (parallel to the $y$-axis). As moving among the city is quite tiresome, Misaka asks you to calculate the minimum distance she has to move to terminate all robots.

Recall that an integer point is a point whose $x$-coordinate and $y$-coordinate are both integers.

输入格式

There are multiple test cases. The first line of the input contains an integer $T$ indicating the number of test cases. For each test case:

The first line contains an integer $n$ ($1 \leq n \leq 10^5)$ indicating the number of robots.

For the following $n$ lines, the $i$-th line contains two integers $x_i$ and $y_i$ ($-10^9 \le x_i, y_i \le 10^9$) indicating the position of the $i$-th robot.

It is guaranteed that the sum of $n$ of all test cases will not exceed $10^5$.

输出格式

For each test case output one line containing one integer indicating the minimum distance Misaka needs to move to terminate all robots.

题目大意

平面上有 $n$ 个点。御坂美琴初始位于 $(0,0)$。她可以随意平行于 $x$ 轴或 $y$ 轴移动，并可以在任意位置使用电磁炮消灭所有 $x$ 或 $y$ 坐标与她相同的点。要消灭所有点，求她最小的移动距离。

$T$ 组数据，$n,\sum n\le 10^5$，$|x_i|,|y_i|\le 10^9$。

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

0
8
4

提示

Note

For the second sample test case, Misaka should first go to $(0, 1)$, then to $(0, 2)$, then to $(0, -3)$, then to $(0, -4)$.

For the third sample test case, Misaka should first go to $(1, 0)$, then to $(1, 1)$, then to $(3, 1)$.