P13461 [GCJ 2008 #1B] Number Sets

你有一个连续整数序列。你希望将它们分组为若干集合。 给定一个区间和一个整数 $P$。最初，区间内的每个整数各自属于一个集合。 然后，你会考虑区间内的每一对整数。如果这两个整数有一个不小于 $P$ 的质因数，则将这两个整数所在的集合合并。 最终，这个过程中会剩下多少个不同的集合？

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

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

**小数据集（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 翻译