You are a cat selling fun algorithm problems. Today, you want to recommend your fun algorithm problems to $k$ cities.

There are a total of $n$ cities, each with two parameters $a_i$ and $b_i$. Between any two cities $i,j$ ($i\ne j$), there is a bidirectional road with a length of $\max(a_i + b_j , b_i + a_j)$. The cost of a path is defined as the total length of roads between every two adjacent cities along the path.

For $k=2,3,\ldots,n$, find the minimum cost among all simple paths containing exactly $k$ distinct cities.

Input

The first line of input contains a single integer $t$ ($1 \leq t \leq 1500$) — the number of test cases.

For each test case, the first line contains a single integer $n$ ($2 \leq n \leq 3\cdot 10^3$) — the number of cities.

Then $n$ lines follow, the $i$-th line contains two integers $a_i,b_i$ ($0 \leq a_i,b_i \leq 10^9$) — the parameters of city $i$.

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

Output

For each test case, print $n-1$ integers in one line. The $i$-th integer represents the minimum cost when $k=i+1$.

Note

In the first test case:

• For $k=2$, the optimal path is $1\to 2$ with a cost of $\max(0+1,2+2)=4$.
• For $k=3$, the optimal path is $2\to 1\to 3$ with a cost of $\max(0+1,2+2)+\max(0+3,3+2)=4+5=9$.

In the second test case:

• For $k=2$, the optimal path is $1\to 4$.
• For $k=3$, the optimal path is $2\to 3\to 5$.
• For $k=4$, the optimal path is $4\to 1\to 3\to 5$.
• For $k=5$, the optimal path is $5\to 2\to 3\to 1\to 4$.