Description

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只好拿这个问题来考考你。

Format

Input

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

Output

一个整数表示答案。

Samples

4 8 6

3