Max Non-Overlapping Events

You are given several test cases. For each test case, you are provided a list of events. Each event is represented by its start time and end time. Your task is to determine the maximum number of non-overlapping events that can be attended.

An event \( [s, e] \) is considered non-overlapping with another event if its start time \( s' \) satisfies \( s' \ge e \) for the previously selected event. A greedy strategy works by sorting the events by their end times, and then repeatedly selecting the next event that starts no earlier than the end time of the last selected event.

Formally, given a sequence of events sorted by their end times \( [s_1, e_1], [s_2, e_2], \ldots, [s_n, e_n] \), select the maximum number of events such that for each selected event \( i_k \) and the subsequent selected event \( i_{k+1} \), the condition \( s_{i_{k+1}} \ge e_{i_k} \) holds.

inputFormat

The input is read from standard input (stdin). The first line contains an integer \( T \) representing the number of test cases. Then for each test case, the first line contains an integer \( N \) indicating the number of events. The following \( N \) lines each contain two space-separated integers \( s \) and \( e \) which denote the start and end times of an event.

outputFormat

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

## sample

1
3
1 2
2 3
3 4

3

</p>