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<\cdots <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