Number Sets

Time limit2sMemory limit512 MB

Summary

Count the connected components formed when numbers A through B are merged whenever they share a prime factor at least P.

Level: Medium7 of 10
Topics: Union-find, Number theory, Math
Solved: No attempts yet

Problem

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.

Input

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

Output

Print the number of sets produced by the rule above.

Examples3

Example 1
Input
```
3 15 3
```
Expected output
```
6
```
Example 2
Input
```
10 20 5
```
Expected output
```
9
```
Example 3
Input
```
10 20 3
```
Expected output
```
7
```