Two professors

There are two professors at the great Academy of X that really do not get along with each other. In order not to reveal their names, we will call them 1 and 2. The Academy employs exactly n professors; each of them has to give exactly one lecture. As their schedules are rather tight (they are professors,
remember?), the starting and the ending time of each lecture is already fixed. However, it is not yet fixed where each lecture will take place. Obviously, it is impossible to schedule two lectures in the same room if their durations overlap; on the other hand, it is possible if one of them starts exactly at the same time that the other one ends. Your tasks is to find the minimal number of rooms allowing to arrange all the lectures. But know that professors 1 and 2 hate each other so much that they will never give their lectures in the same room.

The input contains several test cases. The first line contains the number of test cases t (t <= 250). Each test begins with a line containing the number of professors n (2 <= n <= 10^5). Next n lines follow, i-th of which contains two integers starti and endi (0 <= starti < endi <= 10^9), the starting and the ending time of the lecture that the i-th professor gives, respectively. Total size of the input will not exceed 50MB.

For each test case output the minimal number of rooms necessary to schedule all the lectures.

4
2
0 10
10 20
3
0 10
10 20
10 20
5
4 14
3 13
2 12
1 11
0 10
4
0 10
10 20
20 30
30 40

2
2
5
2

Central European Programming Contest 2008