#include <fstream>
#include <cmath>

using namespace std;
ifstream cin("frac.in");
ofstream cout("frac.out");
long long ciur[110005];
long long vecf[20],cntf=0;
long long sum=0;
void ciurul(long long m)
{
    ciur[0]=1;
    ciur[1]=1;
    for(long long i=4; i<110005; i+=2)
        ciur[i]=1;
    for(long long i=3; i*i<110005; i+=2)
    {
        if(ciur[i]==0)
        {
            for(long long j=i*i; j<110005; j+=2*i)
                ciur[j]=1;
        }
    }
    if(m%2==0)
        vecf[++cntf]=2;
    for(long long i=3; i<110005; i+=2)
        if(ciur[i]==0&&m%i==0)
            vecf[++cntf]=i;
//    for(long long i=1; i<=cntf; i++)
//        cout<<vecf[i]<<" ";
//    cout<<'\n';
}
void backt(long long k,long long n,long long prod,long long nr)
{
    if(k==cntf+1)
    {
        if(nr!=1)
            sum+=pow(-1,nr%2)*(n/prod);
    }
    else
    {
        backt(k+1,n,prod,nr);
        nr++;
        prod*=vecf[k];
        backt(k+1,n,prod,nr);
        nr--;
        prod/=vecf[k];
    }
}
long long solve (long long n)
{
    sum=0;
    backt(1,n,1,1);
    return n-sum;
}
int main()
{
    long long n,p;
    cin>>n>>p;
    ciurul(n);
    cout<<cntf<<'\n';
    long long i1=1,i2=pow(2,61),mij=0,rez=0;
    while(i1<=i2)
    {
        mij=(i1+i2)/2;
        if(solve(mij)>=p)
        {
            rez=mij;
            i2=mij-1;
        }
        else i1=mij+1;
    }
    cout<<rez;
    return 0;
}