TWOPROF - Two Professors

no tags 

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.

Input

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 <= 100000). Next n lines follow, i-th of which contains two integers starti and endi (0 <= starti < endi <= 1000000000), the starting and the ending time of the lecture that the i-th professor gives, respectively.

Output

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

Example

Input:
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

Output:
2
2
5
2

Warning: enormous input/output data, be careful with certain languages


hide comments
flash_nil: 2020-11-29 21:58:29

Why i'm getting WA at test case 3 ?
Can anyone provide any test Case here?

gratitude: 2015-03-01 10:42:17

here given that 1st and 2nd professors hate each other and dont want to teach in the same room

sagar: 2014-11-04 08:51:02

how is the output for 1st case is 2 ?
1 hall can be sufficient


Added by:Fudan University Problem Setters
Date:2009-03-17
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: GOSU
Resource:ACM Central European Programming Contest, Wroc�aw 2008