Maximum Non-overlapping Meetings

You are given several test cases. In each test case, you are given a set of meetings with their start and end times. Two meetings are considered non-overlapping if the start time of a meeting is not less than the end time of the previously selected meeting.

The task is to compute the maximum number of non-overlapping meetings that can be scheduled. This problem can be solved with a greedy approach by sorting meetings by their end times. In mathematical notation, if we denote the meetings as a list of intervals \(\{(s_i, e_i)\}\), after sorting by \(e_i\) (in increasing order), we select an interval \((s_j,e_j)\) if \(s_j \geq e_{prev}\), where \(e_{prev}\) is the end time of the last selected meeting.

inputFormat

The input is read from stdin and has the following format:

T
N1
start_1 end_1
start_2 end_2
... (N1 lines)
N2
start_1 end_1
start_2 end_2
... (N2 lines)
...
NT
start_1 end_1
start_2 end_2
... (NT lines)

Where:

• T is the number of test cases.
• For each test case, N is the number of meetings.
• Each meeting is given by two integers representing its start and end times.

outputFormat

For each test case, output an integer (on a new line) representing the maximum number of non-overlapping meetings that can be scheduled. The output is written to stdout.

## sample

1
3
1 2
2 3
3 4

3

</p>