吴老师出了一个数学题：

    给定 [a,b] 范围内的整数。一开始每个整数都属于各自的集合。每次你需要选择两个属于不同集合的整数，如果这两个整数拥有大于等于 p 的公共质因数，那么把它们所在的集合合并。

    重复如上操作，直到没有可以合并的集合为止。

现在吴老师的问题是，最后变成了多少个集合。

三个数字a,b,p，涵义如上所述

一个数字t表示最终剩下了几个集合

样例 1 解释

对于样例给定的数据，最后有 \{10,20,12,15,18\},\{13\},\{14\},\{16\},\{17\},\{19\},\{11\} 共 7 个集合，所以输出应该为 7。

- 对于 80\% 的数据，1 \leq a \leq b \leq 10^3。

- 对于 100\% 的数据，1 \leq a \leq b \leq 10^5,2 \leq p \leq b。