当前没有测试数据。

合并集合

题目描述

你想将$[a,b]$内的所有自然数分成若干个集合。

一开始每个数自己是一个集合，如果某两个数都是一个$\geq p$的素数的倍数，则将这两个数所在的集合合并，问最后有多少个集合。

输入格式

一行三个整数$a$，$b$，$p$，含意如题。

输出格式

一行一个整数$ans$，表示集合个数。

数据范围与提示

• 对于$50\%$的数据，$1 \leq a \leq b \leq 1000$，$2 \leq p \leq b$；
• 对于$100\%$的数据，$1 \leq a \leq b \leq 10^{12}$，$b \leq a + 10^{6}$，$2 \leq p \leq b$。

样例

10 20 3

7

说明

$12$，$15$，$18$都是$3$的倍数，$10$，$15$，$20$都是$5$的倍数。故$10$，$12$，$15$，$18$，$20$为一个集合，其余的数各为一个集合。

见set.in

见set.out