Exact Divisors

Let K be a positive divisor of M such that K < M. If M is not divisible by K^N, call K an exact divisor of M.

Let d(M) be the number of exact divisors of M. Write a program that computes d(A) + d(A+1) + ... + d(A+B).

The first line contains three integers A, B, and N.

Print the answer on the first line. The answer is always at most 2147483647.

• 1 <= A <= 10^6
• 1 <= B <= 10^7
• 2 <= N <= 10