Number Sets

The consecutive natural numbers from $A$ to $B$ are given. Alice wants to group them into sets.

The sets are built as follows.

• At the start, make one set of size 1 for each number.
• For every pair $(x, y)$ of numbers in the range, if $x$ and $y$ have a common prime factor that is at least $P$, merge the set containing $x$ with the set containing $y$.

For example, take $P = 3$, $A = 3$, $B = 15$. The sets are $\{3, 5, 6, 9, 10, 12, 15\}$, $\{4\}$, $\{7, 14\}$, $\{8\}$, $\{11\}$, $\{13\}$, so the number of sets is 6.

Given $A$, $B$, and $P$, find how many sets this procedure produces.

The first line contains $A$, $B$, and $P$ separated by spaces. ($1 \le A \le B \le 10^{12}$, $B \le A + 10^6$, $2 \le P \le B$)

Print the number of sets produced by the rule above.