#include <iostream>
#include <fstream>
using namespace std;

ifstream f("frac.in");
ofstream g("frac.out");

long long N, P, poz, factori_primi[30];

void desc()
{
    if(N % 2 == 0)
    {
        factori_primi[++poz] = 2;
        do
        {
            N /= 2;
        }
        while(N % 2 == 0);
    }
    for(int d = 3; 1LL * d * d <= N; d += 2)
        if(N % d == 0)
        {
            factori_primi[++poz] = d;
            do
            {
                N /= d;
            }
            while(N % d == 0);
        }
    if(N > 1)
        factori_primi[++poz] = N;
}

long long ff(long long a)
{
    long long ans = 0, limit = (1 << poz), k, product;
    for(int i = 1; i < limit; i++)
    {
        k = 0, product = 1;
        for(int j = 0; j < poz; j++)
            if((1 << j)&i)
                product *= factori_primi[1 + j], k++;
        if(k % 2)
            ans += a / product;
        else
            ans -= a / product;
    }
    return a - ans;
}

long long caut_bin(long long x)
{
    long long p = 1, u = (1LL << 61), ans = 0;
    while(p <= u)
    {
        long long m = (p + u) / 2;
        if(ff(m) >= x)
        {
            ans = m;
            u = m - 1;
        }
        else
            p = m + 1;
    }
    return ans;
}

int main()
{
    f >> N >> P;
    desc();
    g << caut_bin(P);
    return 0;
}