Void Century Mystery

0

0 votes
Easy
Problem

Archaelogists propose theories for a number of events that might have occured during the void century. For a particular event that may have occured, a number of theories are proposed. A number of theories are rendered invalid after a new and more relevant theory surfaces, giving a better and a more valid explanation for the subject of the theory. For this problem, Robin is only concerned with one particular event, lets say, A. For event A, a number of theories were proposed as to  what might have happened.

For a particular theory, the time at which it was proposed be T1 and the time at which it becomes invalid be T2. We define the theory period for this particular theory as [T1T2). Both T1 and T2 are recorded in seconds from some reference point, B. We are given the theory periods for a number of theories. It is possible that more than one theory for event A might be valid at some second, T (Recorded with reference to B ). Let us call the value of the number of valid theories at the second T as popularity of the event at second T. The popularity of the event would be maximum at some point in time. Robin's task is simple, that is calculate this maximum value of popularity for the event A

INPUT:
The first line of the input contains the integer t , the number of test cases.
For each test case first line contains a positive integer n , that is, the number of theories.
Then, n lines follow, one for each theory(1 to n ). Each line contains, 2 integers T1[i] and T2[i]
T1[i] is the lower bound of the theory period for the theory i. (1 <= i <= n )
T2[i] is the upper bound of the theory period for the theory i. (1 <= i <= n )


OUTPUT:
The output contains t lines, one for each test case. Each line contains a positive integer, the required answer for that test case. 

CONSTRAINTS:
1 <= t <= 10
1 <= n <= 104
1 <= T1[i] , T2[i] <= 109
T1[i] < T2[i] 

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

In the sample input, the number of test cases is 1.

For test case 1, the value of n = 5, that is, the number of theories.
The start time and the end time for each theory is measured from the same reference point.
1. The first theory is valid from 1s to 9s (Both Included)
2. Theory 2: It is valid from 2s to 3s (Both Included) 
3. Theory 3: It is valid from 3s to 4s (Both Included)
4. Theory 4: It is valid from 11s to 11s (Both Included)
5. Theory 5: It is valid from 12s to 12s (Both Included)

It can be clearly seen at the time T = 3, a total of 3 theories are valid simultaneously. From time T = 1 to T = 12, the maximum number of simultaneously valid theories is 3. And this event occurs at T = 3 from the common reference.

Editor Image

?