You are given a set
consisting of
disjoint segments of integers. That is,
can be represented as the union of
disjoint intervals of integers
. Let's call a set independent if it has the property that no element of the set is exactly
times another. Please find the size of the largest independent subset of
.
Input Specification
The first line will contain a single integer
.
The next
lines will each contain
integers
and
, representing that
contains all integers in the range
.
Output Specification
Output one integer, the size of the largest independent subset of
.
Constraints


For all pairs
such that
, either
or
.
Subtask 1 [10%]

Subtask 2 [20%]

Subtask 3 [30%]


Subtask 4 [40%]
No additional constraints.
Sample Input
Copy
3
5 7
9 11
1 3
Sample Output
Copy
6
Explanation
In this case,
.
One of the largest independent subsets of
is
.
Comments