Maximum Non-Overlapping Tasks

Given a list of tasks, each defined by its start time and finish time, your goal is to find the maximum number of tasks that can be scheduled without any overlap.

A task is defined as a pair \( (s, f) \) where \( s \) is the start time and \( f \) is the finish time. Two tasks \( (s_1, f_1) \) and \( (s_2, f_2) \) are non-overlapping if \( s_2 \ge f_1 \) (when tasks are arranged in increasing order of finish times).

You are given multiple test cases. For each test case, the input begins with an integer \( T \) indicating the number of tasks. The next \( T \) lines each contain two integers: the start time and the finish time of a task. A test case with \( T = 0 \) indicates the end of input. For each test case, output a single integer representing the maximum number of non-overlapping tasks that can be scheduled.

inputFormat

The input is read from stdin and consists of multiple test cases. Each test case has the following format:

• An integer \( T \) representing the number of tasks.
• Then \( T \) lines follow, each containing two space-separated integers \( s \) and \( f \) representing the start time and finish time of a task.

The input ends when a test case with \( T = 0 \) is encountered.

outputFormat

For each test case, output on a new line a single integer representing the maximum number of non-overlapping tasks that can be scheduled. The output should be written to stdout.

## sample

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

3
3
6

</p>