Maximum Non-Overlapping Trains Scheduling

You are given T test case(s). In each test case, you are provided with an integer N representing the number of trains, followed by 2N space‐separated integers detailing the start and end times of each train. Your task is to select the maximum number of trains that do not overlap. Two trains are considered non-overlapping if the start time of a train is greater than or equal to the end time of the previously selected train. Mathematically, if a train has start time s_i and finish time e_i, then the condition for non-overlap is given by:

$s_i \geq e_{i-1}$

Solve the problem using a greedy algorithm by sorting trains based on their finishing times.

inputFormat

The first line contains an integer T, the number of test cases. Each test case consists of two lines:

• The first line contains an integer N, the number of trains.
• The second line contains 2N space-separated integers where every pair represents the start and end times of a train.

outputFormat

For each test case, output a single line with one integer representing the maximum number of non-overlapping trains that can be scheduled.

## sample

1
3
1 2 3 4 5 6

3

</p>