#5272. 函数

内存限制:128 MiB 时间限制:10 Sec

题目描述

YJC和大火车是好朋友。
有一天,YJC给了大火车一个函数F(n)。
F(n) = (n - 0^2) * (n - 1 ^ 2) * (n - 2 ^ 2) * .... * (n - k ^ 2),其中k是使得n - k^2 > 0的最大整数。
YJC问了大火车一个问题,有多少n属于[L,R],满足P | F(n)。大火车说我用脚丫子就能算出来。
于是YJC只好拿这个问题来考考你。

输入格式

一行三个整数L,R,P。L,R<=10^12,P<=10^6

输出格式

一个整数表示答案。

样例

样例输入


			
4 8 6

样例输出


			
3

数据范围与提示