After years of combing through the archive of the Ancients,

has finally found an interesting problem for the Don Mills Programming Club:Given the x-coordinates of 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 denoting the number of test cases.

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

The next lines of a case each contain space-separated integers: and denoting the x-coordinate of the house, and whether it generates its own power, respectively.

#### Output Specification

Output lines, each containing a single integer on a line by itself, the of which represents the minimum length of wire needed to supply power to all houses for the case.

#### Constraints

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

##### Subtask 1 [30%]

##### Subtask 2 [70%]

#### 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 # and # and houses # and # for a total length of . House # gets power because it is indirectly connected to house # (via house #).

In the second case, house # is the only house which requires power. Since it is closer to house #, the length of the wire required is .

## Comments