[COCI2011-2012#4] BROJ

题目描述

求最小质因数为 $P$ 的不超过 $10^9$ 的第 $N$ 小正整数。

输入格式

第一行，两个整数 $N,P$。保证 $P$ 为质数。

输出格式

输出所求的不超过 $10^9$ 的第 $N$ 小正整数。如果答案超过 $10^9$，则输出 $0$。

样例 #1

样例输入 #1

1 2

样例输出 #1

2

样例 #2

样例输入 #2

2 3

样例输出 #2

9

样例 #3

样例输入 #3

1000 1000003

样例输出 #3

0

提示

【数据规模与约定】

• 对于 $30\%$ 的数据，输出小于 $10^5$（含 $0$）。
• 对于另外 $30\%$ 的数据，$P \gt 1000$。
• 对于 $100\%$ 的数据，$1 \le N,P \le 10^9$。