Description

Little Y and Little S work at the same bookstore. Today, they need to place newly arrived books onto the bookshelves. The bookshelves are arranged in parallel rows, and their positions can be viewed as integer lattice points in the plane coordinate system. The $r$-th row of bookshelves includes points with abscissa $r$ and ordinate $\ge 0$, with the entrance/exit at $(r,0)$.

Each second, they can move to an adjacent integer lattice point in the coordinate system. They can move freely within the same row of bookshelves. However, when moving between different rows of bookshelves, since they are blocked by the shelves, they can only exit via the entrance/exit and detour around the outside of the shelves.

Formally, each second they can move from $(r,c)$ to $(r,c \pm 1)$, or from $(r,0)$ to $(r \pm 1,0)$. But if $c \ge 1$, they cannot move directly from $(r,c)$ to $(r \pm 1,c)$.

There are $n$ new books. The $i$-th book needs to be placed at $(r_i, c_i)$. They start from the warehouse at $(0,0)$, and need to place all the new books onto their corresponding shelves. They can carry any number of books while moving. Upon reaching a shelf at $(r,c)$, they can immediately place all books intended for $(r,c)$ onto the shelf; the time required to place the books on the shelf is negligible.

Now, they want to divide the books into two parts, with each person responsible for one part, and finally return to the starting point $(0,0)$. They want to know how to appropriately assign the books each person is responsible for, so that the time taken by the slower person is minimized.

Input Format

This problem contains multiple test cases.

The first line of input contains a positive integer $T$, representing the number of test cases.

This is followed by $T$ test cases, each formatted as follows:

The first line contains an integer $n$, indicating the number of books.

The next $n$ lines:

The $i$-th line contains two integers $r_i, c_i$, indicating that the $i$-th book should be placed on the bookshelf at $(r_i, c_i)$.

Output Format

For each test case, output a single integer in a line indicating the answer.

1
3
1 2
2 3
3 1

12

Hint

【Sample 1 Explanation】

If Little Y is responsible for the 1st and 3rd books, and Little S is responsible for the 2nd book, they can follow the paths below to reach the corresponding bookshelves and return:

• Little Y: $(0,0) \to (1,0) \to (1,2) \to (1,0) \to (3,0) \to (3,1) \to (3,0) \to (0,0)$, total time taken is $12$ seconds.
• Little S: $(0,0) \to (2,0) \to (2,3) \to (2,0) \to (0,0)$, total time taken is $10$ seconds.

The time taken by the slower person is $12$ seconds. It can be proven that no better solution eLittlests.

【Sample 2】

See siblings2.in and siblings2.ans in the problem attachment.

This sample satisfies the special properties of test data 1, where the first test case satisfies $c_i \le 2$.

【Sample 3】

See siblings3.in and siblings3.ans in the problem attachment.

This sample satisfies the properties of test data 10, where the first test case satisfies $n \le 100$, and the first three test cases satisfy $r_i, c_i \le 100$.

【Data Range】

For all test data, it is guaranteed that: $1 \le T \le 5$, $1 \le n \le 10^5$, $1 \le r_i, c_i \le 500$.

::cute-table{tuack}