History class

Time limit10sMemory limit128 MB

Summary

Find the event order that respects disjoint time order and minimizes the largest position gap between overlapping intervals.

Level: Hard8 of 10
Topics: Intervals, Topological sort, Binary search, Greedy
Solved: No attempts yet

Problem

Hyunsoo is a professor who teaches Korean history at Sogang University. He has $n$ historical events to cover, one per class period, so he has to decide which event belongs in which class.

Event $i$ happened during the interval $[a_i, b_i]$ . Two events are related when their intervals share at least one point. Students understand related events better when the classes covering them sit close together. Two events that are not related must be taught in the order they happened: if A and B are not related and A happened before B, then A has to be taught before B.

The distance between class $i$ and class $j$ is $|i - j|$ . Fix one order of the classes and let $k$ be the largest distance between two related events. Write a program that finds the smallest $k$ over all orders obeying the rule above. If no two events are related, $k$ is $0$ .

Input

The first line contains the number of test cases $T$ .

The first line of each test case contains the number of events $n$ ( $1 \le n \le 50000$ ). Each of the next $n$ lines contains the two endpoints $a_i$ and $b_i$ of the interval of one event ( $-10^9 \le a_i \le b_i \le 10^9$ ). No two events have the same interval.

Output

For each test case, print the smallest $k$ on its own line.

Examples3

Example 1
Input
```
1
3
1 6
2 3
4 5
```
Expected output
```
1
```
Example 2
Input
```
3
1
5 5
2
0 1
2 3
2
0 5
3 7
```
Expected output
```
0
0
1
```
Example 3
Input
```
1
4
1 10
2 3
4 5
6 7
```
Expected output
```
2
```