409776: GYM103741 F K-th Power

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]$$$.

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 a single integer indicating the number of good integers in range of $$$[l,r]$$$.

1 10 2

7

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