NDIV - n-divisors


We all know about prime numbers, prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.

We can classify the numbers by its number of divisors, as n-divisors-numbers, for example number 1 is 1-divisor number, number 4 is 3-divisors-number... etc.

Note: All prime numbers are 2-divisors numbers.

Example:
8 is a 4-divisors-number [1, 2, 4, 8].

Input

Three integers a, b, n.

Output

Print single line the number of n-divisors numbers between a and b inclusive.

Example

Input:
1 7 2

Output:
4

Constraints

1 <= a, b <=10^9
0 <= b - a <= 10^4
1 <= n <= 100


hide comments
(Tjandra Satria Gunawan)(曾毅昆): 2014-04-25 01:37:51

>>again, I got 0.00s alone...
>>@problem setter: how about problem with higher constraints... or change the cluster to pyramid...
>
>cluster was changed , :) ty .

good, now naive and semi-naive implementation will definitely TLE ;-)

Last edit: 2012-12-15 15:26:15
Pranay: 2014-04-25 01:37:51

http://www.spoj.pl/problems/NFACTOR is exactly same with different constraints


Added by:abdelkarim
Date:2012-12-07
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Owner