Problem Description

Find the N-th smallest positive integer not exceeding \(10^9\) whose smallest prime factor is \(P\).

Input Format

The first line contains two integers \(N\) and \(P\). \(P\) is guaranteed to be a prime number.

Output Format

Output the N-th smallest positive integer not exceeding \(10^9\). If the answer exceeds \(10^9\), output \(0\).

Sample Input and Output

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

Notes

[Data Range and Constraints]

• For 30% of the data, the output is less than \(10^5\) (including \(0\)).
• For another 30% of the data, \(P > 1000\).
• For 100% of the data, \(1 \le N, P \le 10^9\).

[Hint and Attribution]

This problem is translated from COCI 2011-2012 CONTEST #4 Task 5 BROJ.

The score for this problem is set according to the original COCI problem, with a maximum score of 140.

见题面 Input 部分

见题面 Output 部分