On a bridge there are $$$n$$$ holes, the $$$i$$$-th hole goes from point $$$a_i$$$ to point $$$b_i$$$. The company in charge of repairing the holes is considering placing wooden pieces to cover the holes. To make the budget, they need to know how many meters of wood they need to cover all the holes, and this number depends on the number of wooden pieces they want to make (a single piece covering all the holes, two pieces covering half and half, one piece for each hole, etc).
Write $$$n$$$ numbers where the $$$i$$$-th number indicates the minimum number of meters needed to cover all the holes with $$$i$$$ wooden pieces.
The input starts with an integer $$$t$$$ indicating the number of cases.
Each case starts with an integer $$$n$$$, followed by $$$n$$$ lines with two integers $$$a_i, b_i$$$.
It holds that $$$a_i \lt b_i$$$ and $$$b_i \lt a_{i+1}$$$.
For each case, write a line with $$$n$$$ integers separated by a space.
$$$1 \leq t \leq 100$$$
21 Points: $$$1 \leq n \leq 100$$$ , $$$0 \leq a_i, b_i \leq 1000$$$
32 Points: $$$1 \leq n \leq 1000$$$ , $$$0 \leq a_i, b_i \leq 10^4$$$
47 Points: $$$1 \leq n \leq 10^4$$$ , $$$0 \leq a_i, b_i \leq 10^9$$$
3 3 0 1 3 5 6 7 7 0 5 9 10 12 15 25 26 30 35 37 38 40 44 5 0 20 21 30 31 40 41 50 55 60
7 5 4 44 34 30 26 24 22 20 60 55 54 53 52
