### 问题描述 小蓝现在拥有区间 $[L,R]$ 范围内的所有整数，开始时每个数字均属于一个集合。现在小蓝可以对集合进行多次或零次操作，操作如下： - 选择两个不属于同一集合的整数，如果它们有大于等于 $p$ 的公共质因子那么将它们所在的两个集合合并。 小蓝的目标是尽可能多的合并集合，使得最后剩下的集合尽可能少，但是小蓝不擅长这个问题，请你帮她解决这个问题。 ### 输入格式 输入一行三个整数，代表 $L,R,p$ 。 ### 输出格式 输出一行一个整数，代表最终集合的数目。 ### 样例输入 ```txt 10 20 3 ``` ### 样例输出 ```txt 7 ``` ### 说明 对于样例，最终有 $\\{10,20,12,15,18\\},\\{13\\},\\{14\\},\\{16\\},\\{17\\},\\{19\\},\\{11\\}$ ，七个集合。 ### 评测数据规模 对于 $50$% 的评测数据 $ 1 \leq L \leq R \leq 10^{3}, 2 \leq p \leq R $ 。 对于 $100$% 的评测数据 $1 \leq L \le R \leq 2 \times 10^{5}, 2 \leq p \leq R $ 。