Merging Sets with Common Prime Factors

You are given all the integers in the range [a, b]. Initially, each integer is in its own set. You need to repeatedly perform the following operation:

Select any two integers from different sets. If these two integers share at least one common prime factor that is at least \(p\) (i.e. a common prime factor \(\geq p\)), merge the sets to which they belong.

Repeat the operation until no more merging is possible. Your task is to determine the number of disjoint sets at the end.

Note: Two integers \(x\) and \(y\) are mergeable if there exists a prime \(q\) with \(q \ge p\) such that \(q\) divides both \(x\) and \(y\). Use union-find and prime sieving techniques to efficiently solve this problem.

inputFormat

The input consists of a single line containing three integers a, b and p (with a ≤ b). The range of integers considered is \([a, b]\).

outputFormat

Output a single integer: the final number of disjoint sets after performing all possible merge operations.

sample

10 20 5

9