Open Intervals

Interview

Time limit1sMemory limit128 MB

Summary

Given up to 50 open intervals per test case, pick the largest subset where no two intervals overlap, counting touching endpoints as compatible.

Level: Medium4 of 10
Topics: Greedy, Sorting, Intervals, Implementation
Solved: No attempts yet

Problem

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.

Input

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$ .

Output

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.

Examples2

Example 1

Input

Expected output

3
2

Example 2
Input
```
4
1 2
2 3
3 4
4 5
0
```
Expected output
```
4
```