Xiao $\Omega$ learned the concept of "powers" in elementary school mathematics: $\forall a, b \in \mathbb{N}^+$, $a^b$ is defined as the product of $b$ copies of $a$.

She is curious about how many positive integers can be represented in the form $a^b$ mentioned above. Since all positive integers $m \in \mathbb{N}^+$ can always be represented as $m^1$, she requires that in the representation above, $b \geq k$, where $k$ is a positive integer she has chosen in advance.

Therefore, she wants to know how many positive integers $x$ in the range $1$ to $n$ can be represented in the form $x = a^b$, where $a$ and $b$ are both positive integers and $b \geq k$.

Input

The input contains two positive integers $n$ and $k$, as described above.

Output

Output a single non-negative integer representing the corresponding answer.

Examples

Input 1

99 1

Output 1

99

Note 1

Since all positive integers $x \in [1, 99]$ can be represented as $x = x^1$, the answer is $99$.

Input 2

99 3

Output 2

7

Note 2

The following are all 7 positive integers that satisfy the condition and 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 represented as $64 = 2^6$. However, according to the problem, different valid representations of the same number are only counted once.

Input 3

99 2

Output 3

12

Note 3

The following are all 12 positive integers that satisfy the condition and 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$

Input 4

power/power4.in

Output 4

power/power4.ans

Input 5

power/power5.in

Output 5

power/power5.ans

Input 6

power/power6.in

Output 6

power/power6.ans

Constraints

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