#include<iostream>
#include<fstream>
using namespace std;
ifstream f("zero2.in");
ofstream g("zero2.out");
unsigned int n,b,i,j,s,k=0,r,p,z=0,v[100],o;
unsigned long int d=0;
int main(){
    for(i=1;i<=10;i++){
        f>>n>>b;
    p=1;
    k=0;
    d=0;
    v[100]={0};
    z=0;
    for(j=1;j<=n;j++){
       for(s=1;s<=j;s++){
        p=p*s;}}

     if(p%b==0){ while(p%b==0){
            k++;
         p=p/b;}
         g<<k<<endl;}
         else g<<0<<endl;}
         return 0;}