F. K-th Power
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Walk_alone hates numbers with large exponents, and he considers an integer $$$x$$$ as good if and only if there does not exist a prime number $$$p$$$, such that $$$x$$$ is a multiple of $$$p^k$$$. He hopes to find the number of all good integers in range $$$[l,r]$$$.

Input

The only line of input contains three integers $$$l,r\ (1 \leq l \leq r \leq 10^{14})$$$ and $$$k\ (2 \leq k \leq 10^9)$$$, indicating the lower range, upper range of the querying interval and the asked $$$k$$$ mentioned above.

Output

Output a single integer indicating the number of good integers in range of $$$[l,r]$$$.

Example
Input
1 10 2
Output
7
Note

In the example above, $$$4$$$ and $$$8$$$ are multiples of $$$2^2$$$, and $$$9$$$ is a multiple of $$$3^2$$$.