题目描述

几何小学的学生学号是一些连续的整数，第一年招收的100人就按1~100来分配学号，第二年从101开始分配....今年是几何小学的二十周年，王校长想要邀请一些校友回来参加活动。王校长邀请了学号从A~B的校友回来，接下来进行的活动需要分组，王校长把分组规则告诉你，问你最后一共会分多少组。
每次选择两个属于不同组的校友，如果他们两个人的学号拥有大于等于P的公共质因数，那么把他们的组进行合并。
反复如上操作，直到没有可以合并的组为止。
每个校友一开始都是独立成组，王校长想知道，最后这些校友会被分成多少组。

输入格式：

一行，三个整数A,B,P。
【数据规模】
A≤B≤100000；
2≤P≤B。

输出格式：

一个数，表示最终会被分为多少组。

输入样例#1：

10 20 3

输出样例#1：

7

样例解释：

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