#### Start

2018-05-02 16:35 UTC

## [email protected] #6 Math

#### End

2018-05-09 16:35 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -327 days 5:10:56

168:00:00

0:00:00

# Problem KNumber Sets (Hard)

Note that this is a harder version of the problem numbersetseasy.

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?

## Input

One line containing an integer $C\leq 10$, 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.

You may assume that $1 \leq A\leq B\leq 10^{12}, B\leq A+1\, 000\, 000$ and $2\leq P\leq B$.

## Output

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.

Sample Input 1 Sample Output 1
2
10 20 5
10 20 3

Case #1: 9
Case #2: 7