## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [Solution] Jumbo Extra Cheese 2 Codeforces Solution

B. Jumbo Extra Cheese 2
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Pak Chanek has $n$ two-dimensional slices of cheese. The $i$-th slice of cheese can be represented as a rectangle of dimensions ${a}_{i}×{b}_{i}$. We want to arrange them on the two-dimensional plane such that:

• Each edge of each cheese is parallel to either the x-axis or the y-axis.
• The bottom edge of each cheese is a segment of the x-axis.
• No two slices of cheese overlap, but their sides can touch.
• They form one connected shape.

Note that we can arrange them in any order (the leftmost slice of cheese is not necessarily the first slice of cheese). Also note that we can rotate each slice of cheese in any way as long as all conditions still hold.

Find the minimum possible perimeter of the constructed shape.

Input

Each test contains multiple test cases. The first line contains an integer $t$ ($1\le t\le 2\cdot {10}^{4}$) — the number of test cases. The following lines contain the description of each test case.

The first line of each test case contains an integer $n$ ($1\le n\le 2\cdot {10}^{5}$) — the number of slices of cheese Pak Chanek has.

The $i$-th of the next $n$ lines of each test case contains two integers ${a}_{i}$ and ${b}_{i}$ ($1\le {a}_{i},{b}_{i}\le {10}^{9}$) — the dimensions of the $i$-th slice of cheese.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot {10}^{5}$.

Output

For each test case, output a line containing an integer representing the minimum possible perimeter of the constructed shape.