A computer program stores the values of its variables in memory.For arithmetic computations, the values must be stored in easilyaccessed locations called registers. Registers areexpensive such that we need to use them efficiently. If twovariables are never used simultaneously, then we can allocate themto the same register. Suppose that there are n variables used ina computer program. For convenience, we useVar = {1, 2,..., n} to represent these n variables.For each variable i, we know the start time s_i andthe finish time f_i when it is used. A variable i isactive during the time interval [s_i, f_i], wheres_i and f_i are two positive integers with s_i < f_i.Two variables i and j can be stored in the same register ifthe corresponding time intervals are disjoint, that is,[s_i, f_i] [s_j, f_j] = . Note that even whens_i < f_i = s_j < f_j, the intervals [s_i, f_i] and[s_j, f_j] are not disjoint. Thus, such variables i and j cannot be placed in the same register. Given a set of n variablesand the corresponding start time and finish time, your task is towrite a computer program to compute the minimum number of usedregisters.

For example, consider Var = {1, 2, 3, 4, 5, 6, 7, 8} and thefollowing table shows the start time and finish time for eachvariable.

Note that variables {1, 3, 6} can be stored in Register A;variables {2, 5, 7} can be stored in Register B; and variables{4, 8} can be stored in Register C. The minimum number of therequired registers equals 3.

Technical Specification

• 1 n 10000.

• For each variable i, 1s_i10000 and 2f_i30000.

Input 

The first line of the input file contains an integer, denoting thenumber of test cases to follow. For each test case, the set ofregisters Var = {1, 2,..., n} is given with thefollowing format: The first line of each test case contains apositive integer n. In the following n lines, each linecontains two positive integers separated by a single space. Thefirst integer represents the start time and the second integerrepresents the finish time.The two positive integers in the i-th line of each test case represent s_i and f_i of variable i.

Output 

For each test case, output the minimum number of the requiredregisters.

Sample Input 

281 23 45 67 89 1011 1213 1415 1661 22 33 44 55 66 7

Sample Output 

12

#include <stdio.h>
#include <stdlib.h>
typedef struct {
    int st, ed;
}Work;
Work Job[10000];
int cmp(const void *i, const void *j) {
    Work *x, *y;
    x = (Work *)i, y = (Work *)j;
    if(x->st != y->st)
        return x->st - y->st;
    return x->ed - y->ed;
}
int main() {
    int t, n, i, j;
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        int ans = 0, tn = n;
        for(i = 0; i < n; i++)
            scanf("%d %d", &Job[i].st, &Job[i].ed);
        qsort(Job, n, sizeof(Work), cmp);

        while(tn) {
            int led = -1;
            for(i = 0, j = 0; i < tn; i++) {
                if(led < Job[i].st) {
                    led = Job[i].ed;
                } else {
                    Job[j++] = Job[i];
                }
            }
            ans ++;
            tn = j;
        }
        printf("%d\n", ans);
    }
    return 0;
}