Find the ~N^\text{th}~ smallest positive integer whose least prime factor is ~P~, or state that the result is greater than ~10^9~.

Input Specification

The first and only line of input contains space separated integers ~N~ and ~P~ ~(1 \le N, P \le 10^9)~. ~P~ will always be prime.

Output Specification

Output a single line with the expected result, or zero if the result exceeds ~10^9~.

Scoring

In test cases worth ~30\%~ of total points, the expected result will either be less than ~100\,000~, or will exceed ~10^9~.

In test cases worth additional ~30\%~ of total points, ~P~ will be greater than ~1\,000~.

Sample Input 1

1 2

Sample Output 1

2

Sample Input 2

2 3

Sample Output 2

9

Sample Input 3

1000 1000003

Sample Output 3

0