#include <bits/stdc++.h>

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

long long m,sol[1001];


long long pinex(long long A)
{
    long long nr,i,prod,j,S=0;
    for(i=1;i<(1<<m);i++)
        {
            nr=0;
            prod=1;
            for(j=0;j<m;j++)
                if((i&(1<<j)))
                {
                    nr++;
                    prod=prod*sol[j+1];
                }

            if(nr%2==1)S=S+A/prod;
            else S=S-A/prod;
        }

        return A-S;
}

long long a,SOL,t,i,j,p,u,nr,mij,prim[10000001],d,b;
bool ciur[10000010];

int main()
{
    f>>a>>b;
    swap(a,b);
    for(d=2; d*d<=10000000; d++)
        if(ciur[d]==0)
        {
            t++;
            prim[t]=d;
            for(i=d*d; i<=10000000; i=i+d)
                ciur[i]=1;
        }

    for(i=1000; i<=10000000; i++)
        if(ciur[i]==0)
        {
            t++;
            prim[t]=i;
        }

    j=1;
    while(prim[j]*prim[j]<=b)
    {
        if(b%prim[j]==0)
        {
            while(b%prim[j]==0)
                b=b/prim[j];
            m++;
            sol[m]=prim[j];
        }
        j++;
    }

    if(b!=1)
    {
        m++;
        sol[m]=b;
    }


    p=1;
    u=12000000000;

    while(p<=u)
    {

        mij=(p+u)/2;
        nr=pinex(mij);


        if(nr>=a){SOL=mij;u=mij-1;}
        else {p=mij+1;}

    }
    g<<SOL;
    return 0;
}