Smallest Prime Factor

Time limit1sMemory limit128 MB

Summary
Given N and prime P, find the N-th positive integer whose smallest prime factor equals P, or print 0 if it exceeds 10^9.
Level

Medium6 of 10

Topics
Number theory, Math, Binary search
Solved
No attempts yet

Problem

List the positive integers whose smallest prime factor is P in increasing order. Find the N-th number in this list.

Input

The first line contains two integers N and P. (1 ≤ N, P ≤ 10^9) P is always prime.

Output

Print the N-th smallest positive integer whose smallest prime factor is P. If that number is greater than 10^9, print 0.

Examples3

  1. Example 1

    Input
    1 2
    Expected output
    2

  2. Example 2

    Input
    2 3
    Expected output
    9

  3. Example 3

    Input
    1000 1000003
    Expected output
    0