P13461 [GCJ 2008 #1B] Number Sets

You start with a sequence of consecutive integers. You want to group them into sets. You are given the interval, and an integer $P$. Initially, each number in the interval is in its own set. Then you consider each pair of integers in the interval. If the two integers share a prime factor which is at least $P$, then you merge the two sets to which the two integers belong. How many different sets there will be at the end of this process?

One line containing an integer $C$, the number of test cases in the input file. For each test case, there will be one line containing three single-space-separated integers $A$, $B$, and $P$. $A$ and $B$ are the first and last integers in the interval, and $P$ is the number as described above.

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

**Small dataset (10 Pts, Test set 1 - Visible)** - $1 \leq C \leq 10$ - $1 \leq A \leq B \leq 1000$ - $2 \leq P \leq B$ **Large dataset (25 Pts, Test set 2 - Hidden)** - $1 \leq C \leq 100$ - $1 \leq A \leq B \leq 10^{12}$ - $B \leq A + 1000000$ - $2 \leq P \leq B$