var f,g:text;
    v,b,d,c:array[0..100000]of longint;
    n,t,baza,max,i,x,j,p,min,s,min2:longint;
begin
assign(f,'zero2.in');reset(f);
assign(g,'zero2.out');rewrite(g);
for t:=1 to 10 do
    begin
    readln(f,n,baza);
    if n>baza then max:=n
           else max:=baza;
    i:=1;
    while ((i*i)shl 1)+(i shl 1)<=max do
          begin
          if (v[i shr 3] shr(i and 7))and 1=0 then
                       begin
                       j:=((i*i)shl 1)+(i shl 1);
                       while 2*j+1<=max do
                             begin
                             v[j shr 3]:=v[j shr 3]or(1 shl(j and 7));
                             j:=j+(i shl 1)+1;
                             end;
                       end;
          inc(i);
          end;
    b[0]:=1;b[1]:=2;
    for i:=1 to max do
        if (v[i shr 3]shr(i and 7))and 1=0 then
                        if 2*i+1<=max then begin
                                         inc(b[0]);
                                         b[b[0]]:=2*i+1;
                                         end;

    for i:=1 to b[0] do
        begin
        for j:=1 to n do
            begin
            if j mod b[i]=0 then d[j]:=d[j div b[i]]+(j div b[i])
                            else d[j]:=d[j-1];
            c[i]:=c[i]+d[j];
            end;
        for j:=1 to n do d[i]:=0;
        end;
    min:=10000;p:=0;
    for i:=1 to b[0] do
        begin
        while baza mod b[i]=0 do
              begin
              inc(d[i]);
              baza:=baza div b[i];
              end;
        if (d[i]>0)and(d[i]<min) then min:=d[i];
        end;
    min2:=10000;
    for i:=1 to b[0] do
        if (d[i]=min)and(c[i]<min2) then min2:=c[i];
    writeln(g,min2 div min);
    for i:=1 to b[0] do
        begin
        c[i]:=0;
        b[i]:=0;
        end;
    end;
close(f);
close(g);
end.