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,

• \(1!=1\)
• \(2!=1\times2=2\)
• \(3!=1\times2\times3=6\)
• \(4!=1\times2\times3\times4=24\)

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!\))?

Input Specification

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\).

Output Specification

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

Sample Output

4
4
3
6
45

Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org