Minimum Stages Allocation Problem

You are given the schedule of several band performances. Each band is represented as an interval \([s, e]\) where \(s\) is the start time and \(e\) is the end time of the performance. The goal is to determine the minimum number of stages required so that no two performances that overlap in time share the same stage.

More formally, for a given set of intervals \(\{[s_i, e_i]\}\), you need to assign each interval to a stage such that if two intervals \([s_i, e_i]\) and \([s_j, e_j]\) are assigned to the same stage, then they satisfy \(e_i \leq s_j\) or \(e_j \leq s_i\). You must compute the minimum number of stages required to schedule all the performances.

Input and Output: The input consists of multiple datasets. Each dataset begins with an integer \(n\) (\(n>0\)) indicating the number of performances, followed by \(n\) lines each containing two integers denoting the start and end times. A line containing a single 0 indicates the termination of input. For each dataset, output the required minimum number of stages on a separate line.

Note: All times are given as integers.

inputFormat

The input is read from standard input (stdin) and consists of one or more datasets. Each dataset is formatted as follows:

 n
 s1 e1
 s2 e2
 ...
 sn en

The input terminates with a line containing a single 0. Here, \(n\) is the number of performances (with \(n > 0\)), and for each performance, two integers \(s\) and \(e\) represent the start and end times respectively.

outputFormat

For each dataset, output a single integer on a new line indicating the minimum number of stages required such that no two overlapping performances are scheduled on the same stage. The output should be written to standard output (stdout).

## sample

4
1 4
2 5
3 7
6 8
0

3

</p>