// Problema Zero 2

#include <stdio.h>

int main()
{
    freopen( "zero2.out", "wt", stdout );
	long int N, B, fac, k, i, j, nr, p;
	freopen( "zero2.in" ,"rt", stdin );
			 for ( i=1; i<=10; i++ )
				 {
						scanf( "%ld %ld", &N, &B );
						fac = 1;
						p =1;
						nr = 0;
						for( k=2; k<=N; k++ )
							{
								fac = fac*p;

								j = fac;
								while( ( j%B == 0 ) )
									{
										nr++;
										j = j/B;
									}
								p = p*k;
							 }
						printf( "%ld\n", nr );
                 }
    fclose( stdin );
    fclose( stdout );    
    return 0;
}