Description

你有一个连续整数序列。你希望将它们分组为若干集合。

给定一个区间和一个整数 $P$。最初，区间内的每个整数各自属于一个集合。

然后，你会考虑区间内的每一对整数。如果这两个整数有一个不小于 $P$ 的质因数，则将这两个整数所在的集合合并。

最终，这个过程中会剩下多少个不同的集合？

Input Format

第一行包含一个整数 $C$，表示测试用例的数量。

对于每个测试用例，有一行包含三个用空格分隔的整数 $A$、$B$ 和 $P$。$A$ 和 $B$ 分别是区间的起始和结束整数，$P$ 如上所述。

Output Format

对于每个测试用例，输出一行，格式为 "Case #$X$: $Y$"，其中 $X$ 是测试用例编号（从 1 开始），$Y$ 是最终集合的数量。

2
10 20 5
10 20 3

Case #1: 9
Case #2: 7

Hint

小数据集（10 分，测试集 1 - 可见）

• $1 \leq C \leq 10$
• $1 \leq A \leq B \leq 1000$
• $2 \leq P \leq B$

大数据集（25 分，测试集 2 - 隐藏）

• $1 \leq C \leq 100$
• $1 \leq A \leq B \leq 10^{12}$
• $B \leq A + 1000000$
• $2 \leq P \leq B$

由 ChatGPT 4.1 翻译