题目描述

给出三个整数 $l,r,k$（$1 \le l \le r \le 2 \cdot 10^9, 2 \le k \le 2 \cdot 10^9$）。

求在区间 $[l,r]$ 内满足 $k \mid i$， 且对于任意 $j \in [2,k-1]$ 都不满足 $j \mid i$ 的数 $i$ 的个数。

输入格式

三个整数 $l,r,k$。

输出格式

一个整数表示答案。

1 10 2

5

12 23 3

2

6 19 5

0