Maximum Non-overlapping Meetings

You are given several sets of meetings. For each set, each meeting is defined by its start time and end time. Two meetings are considered non-overlapping if the start time of one meeting is not less than the end time of the other. Formally, given meetings with start time s_i and end time e_i, two meetings i and j do not overlap if:

\(s_j \ge e_i\) or \(s_i \ge e_j\).

Your task is to determine, for each test case, the maximum number of non-overlapping meetings that can be scheduled. The optimal solution follows a greedy strategy by always picking the meeting that finishes first.

inputFormat

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

• The first line contains an integer T which denotes the number of test cases.
• For each test case, the first line contains an integer N representing the number of meetings.
• This is followed by N lines, each containing two integers representing the start time and end time of a meeting.

For example, an input with two test cases might be:

2
3
1 2
3 4
2 3
3
1 3
2 4
3 5

outputFormat

For each test case, output the maximum number of non-overlapping meetings on a new line to stdout.

For the sample input above, the correct output is:

3
2

## sample

2
3
1 2
3 4
2 3
3
1 3
2 4
3 5

3
2

</p>