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, P$. It is guaranteed that $P$ is a prime number.

Output Format

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

1 2

2

2 3

9

1000 1000003

0

Hint

【Constraints and Notes】

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

【Hints and Explanation】

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

The score of this problem follows the original COCI setting, with a full score of $140$.

Translated by ChatGPT 5