34904번 - Snakey Beavers 서브태스크다국어

문제

Mr. Busy Beaver is very stressed: he has to babysit $N$ baby beavers who are strangely obsessed with arranging themselves into one gigantic snake(?!).

The $i$-th baby beaver starts at a distinct point $(x_i, y_i)$ on an infinite Cartesian plane. Then, they will all start moving. At all times, each beaver's velocity $\vec{v} = (v_x, v_y)$ must satisfy $$ |v_x| \le 1 \quad\text{and}\quad |v_y| \le 1 \quad \text{(cells per second)}. $$ They will only be satisfied once their final positions lie along a path that moves only upward and rightward (i.e., nondecreasing in both $x_i$ and $y_i$). Note that multiple beavers can be at the same point.

Busy Beaver is exhausted, and he just wants to go home. Help him find twice the minimum time required to coordinate these babies into the described snake formation. It can be proven that this value is an integer.

입력

The first line contains a single integer $T$ (1ドル \le T \le 10^4$) --- the number of test cases.

Each test case begins with one integer $N$ (1ドル \le N \le 2 \cdot 10^5$) --- the number of baby beavers.

Each of the next $N$ lines contains two integers $x_i$ and $y_i$ (0ドル \le x_i, y_i \le 10^9$) --- the initial coordinates of the $i$-th beaver.

All $(x_i, y_i)$ in a test case are distinct.

The sum of $N$ over all test cases does not exceed 2ドル \cdot 10^5$.

출력

For each test case, print one integer --- twice the minimum number of seconds needed for the beavers to reach a valid snake formation.

제한

서브태스크

노트

In the sample test case, one way for the beavers to reach a snake formation in 2ドル$ seconds is as follows:

• The beaver at $(5,3)$ can move to $(3,5)$ in 2ドル$ seconds.
• The beaver at $(2,6)$ can move to $(3,6)$ in 1ドル$ second, and then stay there for 1ドル$ second.
• The beaver at $(1,8)$ can move to $(3,6)$ in 2ドル$ seconds.
• The beaver at $(8,5)$ can stay still for 1ドル$ second, and then move to $(8,6)$ in 1ドル$ second.

Afterwards, the beavers will be located at $(3,5),ドル $(3,6),ドル $(3,6),ドル and $(8,6),ドル which lie along a path that moves only upward and rightward.

We can show that it is impossible to form a snake with less time. Therefore, the answer is 2ドル \cdot 2 = 4,ドル twice the minimum number of seconds.