Maximum Non-Overlapping Tasks

You are given several datasets, each containing a list of tasks with their start and end times. Your task is to determine the maximum number of tasks that can be performed without any overlap in each dataset.

A task is represented by its start time \(s\) and finish time \(e\). Two tasks \((s_1, e_1)\) and \((s_2, e_2)\) do not overlap if and only if \(s_2 \geq e_1\). The optimal solution can be obtained by using a greedy algorithm that sorts the tasks in increasing order of their finish times and then selects tasks sequentially.

Input/Output: The problem is interactive using standard input and standard output.

inputFormat

The input is provided via standard input (stdin) with the following format:

T
N1
s1 e1
s2 e2
... (N1 lines for tasks in dataset 1)
N2
s1 e1
s2 e2
... (N2 lines for tasks in dataset 2)
...

Here, \(T\) is the number of datasets. For each dataset, the first line contains an integer \(N\), the number of tasks, followed by \(N\) lines, each containing two space-separated integers \(s\) and \(e\) representing the start and end times of a task.

outputFormat

For each dataset, output a single integer on a new line representing the maximum number of non-overlapping tasks that can be scheduled.

## sample

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

3
2

</p>