Graham is preparing to go trick-or-treating! Halloween is a serious sport. Thus, he wants to find optimal trick-or-treating paths for him and his friends.

Graham lives in a city containing ~T~ neighbourhoods. A neighbourhood consists of ~N~ houses arranged in a line on a street. Each house is either one that gives out candy, or one that doesn't. Every single house that doesn't give out candy is one of his friends' houses. Once one of his friends travels to a house that gives out candy, their house becomes a house that gives out candy.

Being the great friend he is, Graham wants to help his friends figure out the minimum distance such that they can get candy directly, or indirectly from a friend's house. In each neighbourhood, find the sum of all the distances each of his friends in that neighbourhood have to walk.

Input Specification

The first line of the input contains an integer ~T~ denoting the number of neighbourhoods in the city.

The first line of a query contains an integer ~N~, denoting the number of homes arranged in the neighbourhood.

The next ~N~ lines of a query each contain 2 space-separated integers: ~x_i~ and ~p_i~ denoting the x-coordinate of the ~i^{th}~ house and whether it gives out candy or not (~1~ meaning the house gives out candy, ~0~ meaning it doesnt).

Output Specification

Output ~T~ lines, each containing a single integer on a line by itself, the ~i^{th}~ of which represents the minimum distance for the ~i^{th}~ neighbourhood.

Constraints

~1 \le T \le 10~

~1 \le x_1, x_2, \cdots , x_N \le 10^9~

It is guaranteed that at least one home will give out candy.

Subtask 1 [20%]

~1 \le N \le 1000~

Subtask 2 [80%]

~1 \le N \le 10^5~

Sample Input 1

2
3
1 1
2 0
5 0
3
1 1
8 0
9 1

Sample Output 1

4
1

Sample Explanation 1

In the first neighbourhood, the ~2~nd house travels to the first house, travelling a distance of ~1~.

The ~3~rd house now only needs to travel to the ~2~nd house now to get candy indirectly, travelling a distance of ~3~.

Thus, the total distance travelled is ~1+3=4~.