Number Sets (Large)

You are given an interval of consecutive integers and an integer $P$. At the start, every integer in the interval sits in a set of its own.

Look at every pair of integers in the interval. If the two integers have a common prime factor that is at least $P$, merge the two sets that contain them.

Report how many sets are left when the process ends.

The first line contains an integer $C$, the number of test cases.

Each of the next $C$ lines contains three single-space-separated integers $A$, $B$ and $P$. $A$ and $B$ are the first and last integers of the interval, and $P$ is the value described above.

Limits

• $1 \le C \le 100$
• $1 \le A \le B \le 10^{12}$
• $B \le A + 1000000$
• $2 \le P \le B$

For each test case, print one line of the form "Case #X: Y", where $X$ is the test case number starting from 1 and $Y$ is the number of sets.