Open Intervals

You are given $n$ open intervals $(a_1, b_1), (a_2, b_2), \dots, (a_n, b_n)$ on the number line. Each interval represents the start and end time of some activity that needs the same resource. Choose as many intervals as possible so that no two chosen intervals overlap, and report the maximum number of intervals you can choose.

Because the intervals are open, two intervals that meet only at an endpoint — for example $(1, 3)$ and $(3, 5)$ — are considered non-overlapping, so both of them may be chosen.

The input consists of several test cases. The first line of each test case contains a positive integer $n$ ($n \le 50$), the number of intervals. Each of the next $n$ lines contains two positive integers separated by one or more blanks, describing one interval. The end of the input is marked by a line containing a single $0$.

For each test case, print on its own line the largest number of intervals that can be chosen so that no two of them overlap.