B. Big Numbers
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

I don't feel like wasting your time today with long statements, so let's cut straight to the point.

Let $$$p(x)$$$ be the product of all square numbers that divide $$$x$$$, or more formally, $$$p(x) = \displaystyle\prod_{\substack{i = 1 \\ i^2 | x}}^{\infty} i^2$$$.

Given $$$a$$$ and $$$b$$$, your task is to calculate the number of times $$$a!^b$$$ divides $$$p\big(a!^b\big)$$$. More formally, calculate the maximum value of $$$c$$$ such that $$$(a!^b)^c \mid p\big(a!^b\big)$$$.

Since $$$c$$$ can be quite large, print the sum of its digits in base $$$10$$$.

Input

The input consists of the two integers $$$a$$$ and $$$b$$$ $$$(2\leq a \leq 4 \times 10^5, 1 \leq b \leq 10^4)$$$ on a single line.

Output

Print the sum of digits of the maximum value of $$$c$$$ such that $$$(a!^b)^c$$$ divides $$$p\big(a!^b\big)$$$. In particular, we define the sum of digits of $$$c=0$$$ to be $$$0$$$.

Examples
Input
5 3
Output
6
Input
5 5
Output
10
Input
3 1
Output
0
Input
42069 6969
Output
78510
Note

In the first example, $$$5!^3=1728000$$$, and we can check that $$$(5!^3)^6 \mid p(5!^3)$$$ but $$$(5!^3)^7 \nmid p(5!^3)$$$, so the answer is $$$c=6$$$ and the sum of its digits is $$$6$$$.

In the second example, we get $$$c=28$$$, and the sum of its digits is $$$2+8=10$$$.

In the third example, $$$3!^1=6$$$, and $$$p(3!^1)=1$$$, so $$$c=0$$$.