Maximum Non-Overlapping Activities

John wants to attend as many activities as possible. You are given a set of activities, each with a start time \(S\) and a finish time \(E\). Two activities are non-overlapping if the start time of one is not less than the finish time of the other.

This is a classical activity selection problem and can be optimally solved using a greedy algorithm. The approach is to sort the activities by their finish times and then iteratively select each activity that starts no earlier than the finish time of the previously selected activity.

The selection criterion can be expressed as follows:

$$ \text{Select activity } i \text{ if } S_i \geq F_j, $$

where \(S_i\) is the start time of the current activity and \(F_j\) is the finish time of the last selected activity.

inputFormat

The input begins with an integer \(T\), representing the number of test cases. Each test case starts with an integer \(N\), the number of activities, followed by \(N\) lines. Each line contains two integers: the start time \(S\) and the finish time \(E\) of an activity.

outputFormat

For each test case, output one integer on a new line, denoting the maximum number of non-overlapping activities that can be attended.

## sample

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

2
4

</p>