Note that this is an easier version of the problem
numbersetshard.
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
singlespaceseparated 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 1\, 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
