#include <fstream>

using namespace std;
ifstream f("fact.in");
ofstream g("fact.out");
int fact[10000],put[10000],j,q;
int fct(int b,int p)
{
    int nr=0;
    while (b>=p)
    {
        nr+=b/p;
        b/=p;
    }
    return nr;
}
bool ok(int x)
{
    for(int i=1; i<=j; i++)
        if(fct(x,fact[i])<put[i]*q)
            return false;
            return true;
        }
int main()
{
    int p,b,i,pas;
    f>>p>>q;
    pas=1<<30;
    i=2;
    j=0;
    while (i*i<=p)
    {
        if(p%i==0)
        {
            j++;
            fact[j]=i;
            while (p%i==0)
            {
                put[j]++;
                p/=i;
            }
        }
        i++;
    }
    if(p!=1)
    {
        j++;
        fact[j];
        put[j];
    }
    for(i=1;i<=j;j++)
     g<<fact[i]<<" "<<put[i]<<"\n";
    i=0;
    while(pas!=0)
    {
        if(ok(i+pas))
            i+=pas;
        pas/=2;
    }
    b=1+i;
    g<<b;
}