#include <algorithm>
#include <vector>
using namespace std;

#define INF (1<<31)-1
#define pb push_back
#define mp make_pair
#define sc second
#define fs first

vector <pair <int,int> > d;
long long rez;
int n,b;

int numar (int n,int p)
{
    int rez;

    for (rez=0; n; n/=p)
        rez+=n/p;
    return rez;
}

void solve ()
{
    long long nrc;
    int i,j,nr;

    d.clear ();
    for (i=2; i*i<=b; ++i)
        if (b%i==0)
        {
            for (nr=0; b%i==0; b/=i)
                ++nr;
            d.pb (mp (i,nr));
        }
    if (b>1)
        d.pb (mp (b,1));
    rez=INF;
    for (i=0; i<(int)d.size (); ++i)
    {
        nrc=0;
        for (j=1; j<=n; ++j)
            nrc+=numar (j,d[i].fs);
        rez=min (rez, nrc/d[i].sc);
    }
    printf ("%lld\n",rez);
}

int main ()
{
    freopen ("zero2.in","r",stdin);
    freopen ("zero2.out","w",stdout);
    int i;

    for (i=1; i<=10; ++i)
    {
        scanf ("%d%d",&n,&b);
        solve ();
    }

    return 0;
}