var n,b,put,k,j,i,max,t,x:longint;
sum:qword;
f,g:text;

function s(p:longint):qword;
begin
	s:=(((n div p)-1)*(n div p)*p) div 2 + (n div p)*(n mod p+1);
end;
begin
assign(f,'zero2.in');
assign(g,'zero2.out');
reset(f);
rewrite(g);
for k:=1 to 10 do begin
	read(f,n,b);
   i:=1;
   while b<>1 do begin
   	inc(i);
      if b mod i=0 then begin
      	max:=i;
         put:=0;
   		while b mod i=0 do begin
         	b:=b div i;
         	inc(put);
         	end;
         end;
      end;
   b:=max;
	x:=s(b);
   j:=b;
   sum:=0;
   t:=0;
   while x<>0 do begin
		inc(sum,x);
      j:=j*b;
      x:=s(j);
      end;
   writeln(g,sum div put);
   end;	
close(f);
close(g);
end.