Maximum Non-Overlapping Tasks Assignment

You are given a set of tasks, each defined by a start time and an end time. A task is represented as an interval \((s, e)\), where \(s\) is the start time and \(e\) is the end time. A single server can only execute tasks that do not overlap; that is, a task can be executed if its start time \(s\) is not less than the finish time of the last performed task.

Your goal is to determine the maximum number of non-overlapping tasks that can be scheduled for each set of tasks.

The strategy to solve this problem is to use a greedy algorithm: first, sort the tasks by their end times, and then select tasks sequentially, always picking the task with the earliest finish time that does not overlap with the previously selected one.

The input consists of multiple test cases. Each test case begins with an integer \(n\) indicating 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. The input terminates with a test case where \(n = 0\), which should not be processed.

inputFormat

The input is read from standard input (stdin) and contains several test cases. Each test case appears in the following format:

 n
 s1 e1
 s2 e2
 ...
 sn en

Here, \(n\) is the number of tasks, and each of the next \(n\) lines contains two integers \(s_i\) and \(e_i\) representing the start and end times of the \(i\)-th task. The input terminates with a test case where \(n = 0\), which should not be processed.

outputFormat

For each test case, print a single line containing the maximum number of non-overlapping tasks that can be scheduled. The output should be sent to standard output (stdout).

## sample

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

3
2
2

</p>