#include <iostream>

using namespace std;
long long int k,a,s,q,p,st,dr,mij,ras,cnt,x;
struct exponent
{
    long long int fact, ex;
}v[101];
bool rasp(long long int x)
{
    for(long long int i=1;i<=k;i++)
    {
        a=v[i].fact;
        s=0;
        while(x>=a)
        {
            s=s+x/a;
            a=a*v[i].fact;
        }
        if(s<v[i].ex*q) return 0;
    }
    return 1;
}
int cautare_binara()
{
    st=1;
    dr=100;
    while(dr>=st)
    {
        mij=(dr+st)/2;
        if(rasp(mij))
        {
            dr=mij-1;
            ras=mij;
            cout<<mij<<" ";
        }
        else
        {
            st=mij+1;
        }
    }
    return ras;

}
int main()
{
    cin>>p>>q;
    for(int i=2;i*i<=p;i++)
    {
        if(p%i==0) k++;
        cnt=0;
        while(p%i==0)
        {
            p/=i;
            cnt++;
            v[k].fact=i;
        }
        v[k].ex=cnt;
    }
    if(p!=1)
    {
        k++;
        v[k].fact=p;
        v[k].ex=1;
    }
    for(int i=1;i<=k;i++)
    {
        cout<<v[i].fact<<" "<<v[i].ex;
        cout<<'\n';
    }
    cout<<cautare_binara();
    return 0;
}