Maximum Non-Overlapping Events

You are given several test cases. In each test case, there is an integer \(n\) representing the number of events, followed by \(n\) lines each containing two integers \(s\) and \(e\) which denote the start and end times of an event. Your task is to determine the maximum number of non-overlapping events that can be attended. An event \(i\) is represented by the interval \([s_i, e_i]\). Two events are considered non-overlapping if the start time of one event is not less than the finish time of the previously selected event.

Hint: A greedy algorithm that always picks the event that finishes first works well for this problem.

inputFormat

The input begins with an integer \(T\) on a separate line, representing the number of test cases. For each test case, the first line contains an integer \(n\), the number of events. The next \(n\) lines each contain two space-separated integers \(s\) and \(e\) indicating the start time and end time of an event, respectively.

Example:

2
3
1 5
2 6
8 10
4
1 3
2 4
3 5
8 9

outputFormat

For each test case, output a single integer on a new line representing the maximum number of non-overlapping events that can be attended.

Example:

2
3

## sample

2
3
1 5
2 6
8 10
4
1 3
2 4
3 5
8 9

2
3

</p>