Maximum Non-Overlapping Events

You are given several datasets, each containing a list of events characterized by their start and end times. For each dataset, determine the maximum number of events that can be attended without any overlaps.

An event \(e_i\) defined by a start time \(s_i\) and end time \(f_i\) does not overlap with another event \(e_j\) if and only if \(s_j \ge f_i\). Using a greedy algorithm based on sorting by finish times is a typical method to solve this problem.

The input will contain multiple datasets. Each dataset begins with an integer \(n\) (the number of events). The next \(n\) lines each contain two integers representing the start and end times of an event. The input terminates with a dataset whose \(n = 0\) (this dataset should not be processed).

inputFormat

The input is read from stdin and consists of multiple datasets. Each dataset is structured as follows:

• The first line contains a single integer \(n\) representing the number of events in the dataset.
• The following \(n\) lines each contain two space-separated integers \(s\) and \(f\) representing the start and end times of an event.

The input ends with a line containing a single 0, which should not be processed.

outputFormat

For each dataset (except the terminating one), output the maximum number of non-overlapping events that can be attended. The results should be printed on a single line, separated by a space. The output is written to stdout.

## sample

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

2 3

</p>