T4 归类游戏

时间：1s

空间：256M

题目描述

一群小朋友在玩一个游戏。每个小朋友记住一个数字，这个数字是整数，小朋友之间的数字是不一样的。如果两个小朋友的数字含有大于等于 $P$ 的公共质因数，这两个小朋友要归类到一个团体里。如果选择两个属于不同团体的小朋友，他们的数字也满足含有大于等于 $P$ 的公共质因数，这两个团体也要合并。只要满足条件的团体，都要进行归类合并。

已知小朋友的数字编号是从 $X$ 到 $Y$，请你计算最后有几个团体。

输入格式

第一行输入三个正整数 $X,Y,P$ 。

输出格式

输出最后团体的个数。

样例输入输出

input1:

10 20 3

output2:

7

说明/提示

最后的团体是：{10,12,15,18,20}，{11}，{13}，{14}，{16}，{17}，{19}。

数据范围

对于 $30\%$ 的数据，满足 $X \le Y \le 1000$。

对于 $100\%$ 的数据，满足 $X \le Y \le 10^5,2 \le P \le Y$。