After years of combing through the archive of the Ancients, Phoenix1369 has finally found an interesting problem for the Don Mills Programming Club:

Given the x-coordinates of ~N~ houses arranged in a row, some of which can generate their own power, output the minimum length of electrical wire required to connect every home to a source of power, either directly or indirectly.

Input Specification

The first line of the input contains an integer ~T~ denoting the number of test cases.

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

The next ~N~ lines of a case each contain ~2~ space-separated integers: ~x_i~ and ~p_i~ ~(1 \le i \le N)~ denoting the x-coordinate of the ~i^\text{th}~ house, and whether it generates its own power, respectively.

Output Specification

Output ~T~ lines, each containing a single integer on a line by itself, the ~j^\text{th}~ of which represents the minimum length of wire needed to supply power to all houses for the ~j^\text{th}~ case.

Constraints

~1 \le T \le 10~

~1 \le x_1 < x_2 < \dots < x_N \le 10^9~

~p_i \in \{0, 1\}~

It is guaranteed that at least one home will be able to generate its own electricity.

Subtask 1 [30%]

~1 \le N \le 1000~

Subtask 2 [70%]

~1 \le N \le 10^5~

Sample Input

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

Sample Output

4
1

Explanation

In the first case, wires can be added between houses #~1~ and #~2~ and houses #~2~ and #~3~ for a total length of ~1+3 = 4~. House #~3~ gets power because it is indirectly connected to house #~1~ (via house #~2~).

In the second case, house #~2~ is the only house which requires power. Since it is closer to house #~3~, the length of the wire required is ~9-8 = 1~.

Original Problem Author: admin2; Problem Resource: CodeChef