34461번 - Traveling Salesman Problem 다국어

문제

There are $N$ cities numbered from 1ドル$ to $N,ドル the $i$-th of which is at coordinates $(x_i, y_i)$.

Busy Beaver wants to start at city 1ドル,ドル visit every city exactly once, and return to city 1ドル$.

To go from city $i$ to city $j,ドル it takes $|x_i - x_j + y_i - y_j|$ seconds. Find the minimum number of seconds for Busy Beaver to complete his trip.

입력

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

The first line of each test case contains a single integer $N$ (2ドル \leq N \leq 2 \cdot 10^5$) --- the number of cities.

The $i$-th of the next $N$ lines of each test case contains two integers $x_i$ and $y_i$ ($-10^9 \leq x_i, y_i \leq 10^9$) --- the coordinates of the $i$-th city.

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

출력

For each test case, output a single integer --- the minimum number of seconds needed for Busy Beaver to complete his trip.

제한

노트

In the first test case, we can take the path 1ドル \xrightarrow{3,円\text{seconds}} 3 \xrightarrow{1,円\text{second}} 4 \xrightarrow{1,円\text{second}} 5 \xrightarrow{3,円\text{seconds}} 2 \xrightarrow{2,円\text{seconds}} 1$ which takes 3ドル+1+1+3+2=10$ seconds.