Description

Caima gives you all integers in the range $[a,b]$. Initially, each integer belongs to its own set. Each time, you may choose two integers from different sets; if these two integers have a common prime factor greater than or equal to $p$, merge the sets that contain them.

Repeat the operation above until no more sets can be merged.

Now Caima wants to know how many sets remain in the end.

Input Format

One line containing three integers $a,b,p$, separated by spaces.

Output Format

A single integer, the number of sets in the end.

10 20 3

7

Hint

Explanation for Sample 1

For the given sample, the final sets are {10, 20, 12, 15, 18}, {13}, {14}, {16}, {17}, {19}, {11}, so there are 7 sets in total and the output should be 7.

Constraints

• For 80% of the testdata, $1 \leq a \leq b \leq 10^3$.
• For 100% of the testdata, $1 \leq a \leq b \leq 10^5$, $2 \leq p \leq b$.

Translated by ChatGPT 5