Problem Description

In elementary math class, Little $\Omega$ learned the concept of “powers”: $\forall a, b \in \N^+$, define $a^b$ as the product of $b$ copies of $a$ multiplied together.

She is curious about how many positive integers can be written in the form $a^b$ above. Since every positive integer $m \in \N^+$ can always be written as $m^1$, she requires that in such a representation, we must have $b \geq k$, where $k$ is a positive integer chosen in advance.

Therefore, she wants to know: among the integers from $1$ to $n$, how many positive integers $x$ can be written as $x = a^b$, where $a$ and $b$ are both positive integers and $b \geq k$?

Input Format

The first line contains two positive integers $n, k$, with the meanings described above.

Output Format

Output one line containing one non-negative integer representing the corresponding answer.

99 1

99

99 3

7

99 2

12

Hint

[Explanation for Sample 2]

The following are all $7$ positive integers that satisfy the requirement, along with one valid representation for each.

$1 = 1^3, 8 = 2^3, 16 = 2^4, 27 = 3^3, 32 = 2^5, 64 = 4^3, 81 = 3^4$.

Note that some positive integers may have multiple valid representations. For example, $64$ can also be written as $64 = 2^6$.

However, according to the statement, different valid representations of the same number are counted only once.

[Explanation for Sample 3]

The following are all $12$ positive integers that satisfy the requirement, along with one valid representation for each.

$1 = 1^2, 4 = 2^2, 8 = 2^3, 9 = 3^2, 16 = 4^2, 25 = 5^2, 27 = 3^3, 32 = 2^5, 36 = 6^2, 49 = 7^2, 64 = 8^2, 81 = 9^2$.

[Sample 4]

See power/power4.in and power/power4.ans in the contestant directory.

[Sample 5]

See power/power5.in and power/power5.ans in the contestant directory.

[Sample 6]

See power/power6.in and power/power6.ans in the contestant directory.

[Constraints]

For all testdata, it is guaranteed that $1 \leq n \leq 10^{18}$ and $1 \leq k \leq 100$.

Translated by ChatGPT 5