시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB111100.000%

문제

Let B be a positive integer. A natural number n is called B-smooth, if in its factorisation into primes there is no prime factor greater then B. We may say equivalently that a number n is called B-smooth, if it may be represented as a product of positive integers less then or equal to .

Write a program which:

  • reads from the standard input three positive integers n, m and B,
  • determines the number of all B-smooth numbers in the interval [n,n+m] (inclusive),
  • writes the result to the standard output.

입력

In the first line of the standard input there are three integers n, m and B, separated by single spaces, 1 ≤ n ≤ 2,000,000,000, 1 ≤ m ≤ 100,000,000, 1 ≤ B ≤ 1,000,000.

출력

Your program should write one integer in the first line of the standard output. It should be the determined number of B-smooth numbers.

예제 입력 1

30 10 5

예제 출력 1

4