# 2187. 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.

• $1 \le C \le 100$
• $1 \le A \le B \le 10^{12}$
• $B \le A + 1~000~000$
• $2 \le P \le B$

### 输出格式

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.

### 样例

Input
2
10 20 5
10 20 3
Output
Case #1: 9
Case #2: 7

2 人解决，12 人已尝试。

2 份提交通过，共有 49 份提交。

9.8 EMB 奖励。