合并集合

题目描述

Orange拥有 $[l,r]$ 之间所有的整数，他把他们分别分类到各自的集合，即 $\{1\} \{2\} \cdots \{n\}$，现在，Orange会执行如下操作：

1. 给你一个质数 $p$。
2. 选择任意两个集合 $S_1, S_2$，当且仅当他们满足 $\exist u \in S_1, v \in S_2$，对于 $u,v$，$\exist q \in \mathbb{P}$ 且 $q \ge p$，有 $q | \gcd(u,v)$，Orange将合并这两个集合。
3. 重复 操作2 ，直到没有集合可以被合并。

Orange想问你最后会剩下多少个集合。

输入格式

第一行包含三个整数 $l,r,p$。

数据范围

$1\le l \le r\le 10^5$ $p\le b 且 p \in \mathbb{P}$

$\mathbb{P}$表示质数全集。

输出格式

一个整数表示答案。

样例 #1

样例输入 #1

10 20 3

样例输出 #1

7

提示

样例 1 解释

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