Minimum Stage Scheduling

You are given several test cases. In each test case, there are multiple performances, each with a starting time and an ending time. Performances on the same stage cannot overlap. Your task is to determine the minimum number of stages required so that all performances can be scheduled without any overlap on the same stage.

Formally, for each test case, you are given an integer \(N\) and then \(N\) pairs of integers \((s_i, e_i)\) representing the start and end times. Two performances \((s_i, e_i)\) and \((s_j, e_j)\) are considered to overlap if \(e_i > s_j\) and \(s_i < e_j\) (assuming \(s_i \le e_i\) and \(s_j \le e_j\)). Determine the minimum number of stages required so that no two overlapping performances are scheduled on the same stage.

Input and Output via standard input (stdin) and standard output (stdout).

inputFormat

The input begins with an integer \(T\) denoting the number of test cases. For each test case, the first line contains an integer \(N\) denoting the number of performances. This is followed by \(N\) lines, each containing two space-separated integers representing the start and end times of a performance.

Example:

2
3
1 4
2 5
9 12
4
5 8
4 6
3 7
1 5

outputFormat

For each test case, output a single integer on a new line representing the minimum number of stages required so that no overlapping performances occur on the same stage.

Example Output:

2
3

## sample

1
3
1 4
2 5
9 12

2

</p>