Exam Preparation

Interview

Time limit1sMemory limit128 MB

Summary

Schedule preparation days before each exam day and find how many days before the earliest exam study must start.

Level: Medium4 of 10
Topics: Greedy, Sorting
Solved: No attempts yet

Problem

Hektor has a great many exams this semester. Each exam is described by two integers: the day on which it is held, and the number of days he must spend preparing for it.

Hektor can prepare for only one exam on any single day, and one day of study covers one required preparation day for that exam. Every exam's preparation must be finished on or before the day the exam is held. Hektor may also prepare for an exam on the very day he sits it, because he studies early in the morning while exams take place around noon.

Work out how many days before his earliest exam Hektor must start studying so that he can finish preparing for every exam in time.

Input

The first line contains the number of test groups $Z$ ( $1 \le Z \le 10$ ). The descriptions of the test groups follow.

The first line of a single test group contains an integer $N$ ( $1 \le N \le 100000$ ), the number of exams. Each of the next $N$ lines contains two positive integers smaller than $10001$ describing one exam. The first is the day on which the exam is held, and the second is the number of days needed to prepare for it (that is, $1 \le d, p \le 10000$ ).

Output

For each test group, print on its own line how many days before that group's earliest exam Hektor must begin studying.

Examples1

Example 1
Input
```
2
1 
3 1
2
6 3
5 2
```
Expected output
```
0
3
```