409224: GYM103463 D Dup4 and pebble pile

Dup4 has a large number of pebbles. He numbered them $$$a$$$ through $$$b$$$.

Initially, each pebble forms a pile of its own.

But Dup4 hates so many piles. So he can do the following operation to merge the two piles.

Every time, He chooses two pebbles $$$x$$$ and $$$y$$$. If $$$x$$$ and $$$y$$$ have a common prime factor $$$t$$$, and $$$t$$$ greater or equal than $$$p$$$. He can merge the pile of pebbles where $$$x$$$ is and the pile of pebbles where $$$y$$$ is. The premise is that $$$x$$$ and $$$y$$$ belong to two different piles.

He will repeat the above operations until he can no longer merge.

Finally, Dup4 wants to know how many pebble piles will end up.

For instance, if we consider $$$a = 10, b = 20, p = 3$$$, the final result will be:

$$$$$$ [10, 12, 15, 18, 20], [11], [13], [14], [16], [17], [19] $$$$$$

There are $$$7$$$ piles.

The first line contains three integers $$$a, b, p(1 \leq a \leq b \leq 10^5, 2 \leq p \leq b)$$$.

Print a single integer in one line: the number of pile in the end.

10 20 3

7