Number Sets (Large)

A block of consecutive integers is split into sets by the procedure below.

You are given the interval of integers to work on and an integer $P$. At the start, every integer in the interval belongs to a separate set that holds only that integer. Then, for every pair of integers in the interval, if the two integers have a common prime factor that is at least $P$, the two sets holding them are merged into one set.

How many sets are there when the procedure ends?

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

Each test case is one line with three integers $A$, $B$, $P$ separated by spaces. $A$ and $B$ are the first and the last integer of the interval, and $P$ is the number described above.

Constraints

• $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.