A computer program stores the values of its variables in memory. For arithmetic computations, the values must be stored in easily accessed locations called registers. Registers are expensive such that we need to use them efficiently. If two variables are never used simultaneously, then we can allocate them to the same register. Suppose that there are n variables used in a computer program. For convenience, we use Var = {1, 2,..., n} to represent these n variables. For each variable i, we know the start time s_i and the finish time f_i when it is used. A variable i is active during the time interval [s_i, f_i], where s_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 if the corresponding time intervals are disjoint, that is, [s_i, f_i] [s_j, f_j] = . Note that even when s_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 variables and the corresponding start time and finish time, your task is to write a computer program to compute the minimum number of used registers.

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

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 the required 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 the number of test cases to follow. For each test case, the set of registers Var = {1, 2,..., n} is given with the following format: The first line of each test case contains a positive integer n. In the following n lines, each line contains two positive integers separated by a single space. The first integer represents the start time and the second integer represents 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 required registers.

Sample Input 

2
8
1 2
3 4
5 6
7 8
9 10
11 12
13 14
15 16
6
1 2
2 3
3 4
4 5
5 6
6 7

Sample Output 

1
2

#include <stdio.h>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
struct var {
    int s, f;
};
struct cmp2 {
    bool operator() (int x, int y) {
        return x - y > 0;
    }
};
bool cmp(var i, var j) {
    if(i.s != j.s)
        return i.s - j.s < 0;
    return i.f - j.f < 0;
}
int main() {
    int t, n, i;
    var V[10000];
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        for(i = 0; i < n; i++) {
            scanf("%d %d", &V[i].s, &V[i].f);
        }
        sort(V, V+n, cmp);
        priority_queue<int, vector<int>, cmp2> pQ;
        int ans = 0, end;
        for(i = 0; i < n; i++) {
            while(!pQ.empty()) {
                end = pQ.top();
                if(end < V[i].s) {
                    pQ.pop();
                } else {
                    break;
                }
            }
            pQ.push(V[i].f);
            if(pQ.size() > ans)
                ans = pQ.size();
        }
        printf("%d\n", ans);
    }
    return 0;
}