Number Sets

Given an interval [A, B] and a prime threshold P, merge any two numbers sharing a prime factor >= P, then count the remaining sets.

Medium6Union-findNumber theoryMathNo attempts yetTime limit5sMemory limit512 MB

Description

Examples2

Problem

You are given an interval of consecutive integers. You want to group these integers into sets.

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

Then you consider every pair of integers in the interval. If the two integers share a prime factor that is at least $P$ , you merge the two sets the integers belong to.

How many sets are left when this process is finished?

Input

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

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

Limits

$1 \le C \le 10$
$1 \le A \le B \le 1000$
$2 \le P \le B$

Output

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