The factorial of a number ~N~, denoted as ~N!~, is equal to the product of all natural numbers up to and including ~N~. For example,
Given two numbers ~K~ and ~M~, what is the smallest value of ~N~ such that ~N!~ has at least ~M~ factors of ~K~ (that is, ~K^M~ divides evenly into ~N!~)?
The standard input will contain 10 datasets. Each dataset contains two integers ~K~, ~M~ ~(2 \le K,M \le 1\,000\,000)~.
For the first 4 cases, ~K~ is prime and ~K \times M \le 1\,000~.
For the first 7 cases, ~K \times M \le 1\,000\,000~.
For each dataset, output the minimum value of ~N~ such that ~N!~ has at least ~M~ factors of ~K~.
Sample Input (Five Datasets Shown)
2 2 2 3 3 1 4 2 10 10
4 4 3 6 45
Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org