### 问题描述

小蓝现在拥有区间 $[L,R]$ 范围内的所有整数，开始时每个数字均属于一个集合。现在小蓝可以对集合进行多次或零次操作，操作如下：

• 选择两个不属于同一集合的整数，如果它们有大于等于 $p$ 的公共质因子那么将它们所在的两个集合合并。

小蓝的目标是尽可能多的合并集合，使得最后剩下的集合尽可能少，但是小蓝不擅长这个问题，请你帮她解决这个问题。

输入格式

输入一行三个整数，代表 $L,R,p$ 。

输出格式

输出一行一个整数，代表最终集合的数目。

样例输入

10 20 3

样例输出

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$ 。