Maximum Non-overlapping Meetings

You are given several test cases, each containing a list of meetings with their start and end times. Your task is to determine the maximum number of meetings that can be scheduled without overlapping. A meeting is considered non-overlapping if its start time is not less than the end time of the previous meeting chosen.

You should implement a greedy algorithm: sort the meetings by their end times and then select the maximum number of meetings such that none of them overlap.

Input/Output: The input is provided via standard input (stdin) while the output should be printed to standard output (stdout).

inputFormat

The first line of input contains an integer T representing the number of test cases. For each test case:

1. The first line contains an integer n denoting the number of meetings.
2. The following n lines each contain two space-separated integers representing the start and end times of a meeting.

outputFormat

For each test case, output a single integer on a new line that represents the maximum number of non-overlapping meetings that can be scheduled.

2
3
1 2
3 4
0 6
4
1 3
2 4
3 5
7 8

2
3