#include <stdio.h>
#include <stdlib.h>

int lejandre(int n,int div){
    int rez, nr;
    rez=0;
    nr=div;
    while(nr<=n){
        rez=rez+(n/nr);
        nr*=div;
    }
    return rez;
}

int lejandrei(int n, int b, int p){
    int i, rez;
    rez=0;
    for(i=1;i<=n;i++)
        rez=rez+lejandre(i,b);
    return rez/p;
}

int main()
{
    int n, b, min, i, div, x, p;
    FILE *fi=fopen("zero2.in", "r"), *fo=fopen("zero2.out", "w");
    for(i=0;i<10;i++){
        min=2000000000;
        fscanf(fi, "%d%d", &n, &b);
        div=2;
        while(div*div<=b){
            if(b%div==0){
                p=0;
                while(b%div==0){
                    b/=div;
                    p++;
                }
                x=lejandrei(n,div,p);
                if(x<min)
                    min=x;
            }
            div++;
        }
        if(b!=1){
            x=lejandrei(n,b,1);
            if(x<min)
                min=x;
        }
        fprintf(fo, "%d\n", min);
    }
    return 0;
}