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 .
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 one integer, the size of the largest independent subset of .
For all pairs such that , either or .
Subtask 1 [10%]
Subtask 2 [20%]
Subtask 3 [30%]
Subtask 4 [40%]
No additional constraints.
3 5 7 9 11 1 3
In this case, .
One of the largest independent subsets of is .