Problems
Factorial
Factorial
Factorials of natural numbers \textbf{N} (denoted \textbf{N!}) is the product of all integers from \textbf{1} to \textbf{N}, inclusive: \textbf{N!}\textit{\textbf{ = }}\textbf{1}\textit{\textbf{×}}\textbf{2}\textit{\textbf{×}}\textbf{3}\textit{\textbf{×…×}}\textbf{N}.
Required to determine how many digits "\textbf{0}" end record number \textbf{N!} in \textbf{K}-ary number system.
\InputFile
In the input file contains two numbers: \textbf{N}\textit{\textbf{ }}and\textit{\textbf{ }}\textbf{K}\textit{\textbf{ }}(\textbf{1}\textit{\textbf{ ≤ }}\textbf{N}\textit{\textbf{ ≤ }}\textbf{10^9}\textit{\textbf{, }}\textbf{2}\textit{\textbf{ ≤ }}\textbf{K}\textit{\textbf{ ≤ }}\textbf{5000}).\textit{\textbf{ }}Both numbers are written in decimal notation.
\OutputFile
In the output file to bring the number of zeros, which in the \textbf{K}-ary number system ends with the number \textbf{N!}. Number of output in the decimal system.
Input example #1
10000 10
Output example #1
2499