uses Math;

var a,n,t1,t2,i,t3,t4,x1,x2,max,ans,t5 : longint;

procedure no;
begin
writeln(0);
halt(0);
end;

procedure calc(i : longint);
begin
{        if t2 mod i = 0 then
                if t1 mod i <> 0 then
                        no else
                                begin}
                                        t3 := 0;
                                        t4 := 0 ;
					if t1 mod i <> 0 then no;
                                        while t2 mod i = 0 do begin t2 := t2 div i; inc(t3);end;
                                        while t1 mod i = 0 do begin t1 := t1 div i; inc(t4);end;
                                        if ceil(t3/t4) > max then
                                                begin
                                                        max := ceil(t3/t4);
                                                        x1 := t3;
                                                        x2 := t4;
                                                        t5 := i;
                                                end;
//                                end;
end;

begin
assign(input,'h.in');
assign(output,'h.out');
reset(input);
rewrite(output);
readln(a,n);
if a mod n = 0 then begin writeln(1); HALT(0); END;
t1 := a;
t2 := n;
{for i := 2 to n div 2 do
        calc(i);}
i := 2;
while i <= (n div 2) do
	begin if t2 mod i = 0 then calc(i); inc(i);end;
if t2 <> 1 then calc(n);
ans := 1;
while x1 > x2 do
        begin
        inc(ans);
        x1 := trunc(LogN(t5,x1));
        end;
        writeln(ans);
end.