Problem Description

There are $n$ groups of coins, and the $i$-th group contains two coins valued at $a_i$ and $b_i$. Now you want to pick exactly $k$ coins out of them. However, there is a restriction - you can not pick the second coin valued at $b_i$ in the $i$-th group without picking the other one in the same group. In other words, in the $i$-th group, you can
- pick none of the two coins;
- pick only the first one valued at $a_i$; or
- pick both of them.

We now want to know the maximum sum of the $k$ picked coins' values, denoted by $f(k)$.

Furthermore, we want to know $f(1), f(2), \cdots, f(2n)$.

Input

The input contains several test cases, and the first line contains a single integer $T~(1 \le T \le 90)$, the number of test cases.

For each test case, the first line contains an integer $n~(1 \le n \le 100\,000)$, indicating the number of coin groups.

Each of the following $n$ lines contains two integers $a_i,b_i~(1 \le a_i, b_i \le 10\,000)$ indicating the coin values in that group.

It is guaranteed that the sum of $n$ in all test cases does not exceed $2\,100\,000$.

Output

For each test group, just output $2n$ integers in a single line representing $f(1), f(2), \cdots, f(2n)$, and adjacent integers should be separated by one space.

2
3
1 2
1 4
4 2
2
1 3
3 2

4 6 9 11 12 14
3 5 7 9