Minimum Operating Rooms

You are given a series of test cases. Each test case consists of a list of surgeries represented by their start time and end time. Your task is to determine the minimum number of operating rooms required so that all surgeries can be performed without any time conflicts.

A surgery is represented by an interval \([s, t]\), where \(s\) is the start time and \(t\) is the end time. Two surgeries are said to overlap if they share any common time. Note that if one surgery ends exactly when another begins, they do not overlap.

This problem can be mathematically framed as finding the maximum number of overlapping intervals at any point in time. In \(\LaTeX\), the maximum number of operating rooms required is given by:

[ \text{max_rooms} = \max_{t} \left( \sum_{i=1}^{n} \mathbf{1}_{{s_i \le t < t_i}} \right) ]

inputFormat

The input is read from standard input (stdin). It consists of several test cases. For each test case, the first line contains an integer \(n\) indicating the number of surgeries. Each of the following \(n\) lines contains two integers \(s\) and \(t\) representing the start and end times of a surgery. The sequence of test cases terminates with a line containing a single zero.

outputFormat

For each test case, output a single line containing one integer: the minimum number of operating rooms required.

## sample

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

3
1

</p>