type vector=array[1..100] of 0..1;
var  f,g:text;
     a,b,c,m,n,p,lv,i,j:int64;
     x:vector;
     v:array[1..100] of longint;
function prime(n,c:int64):boolean;
    begin
      While n<>c do
        if n>c then n:=n-c
           else c:=c-n;
        if c=1 then prime:=true
          else prime:=false;
    end;
procedure adauga(var x:vector);
          begin
            if x[lv]=0 then x[lv]:=1
                 else
                    begin
                      x[lv]:=0;
                      j:=lv-1;
                      while x[j]=1 do
                          begin
                            x[j]:=0;
                            dec(j);
                          end;
                       x[j]:=1;
                    end;
          end;

function ver(c:int64):longint;
     var w,q,pp:int64;
        ok:boolean;
    begin
      w:=c;
      fillchar(x,lv,0);
      ok:=true;
      while ok do
         begin
           adauga(x);
           q:=0;
           pp:=1;
           for j:=1 to lv do if x[j]=1 then begin inc(q); pp:=pp*v[j]; end;
           if q mod 2=0 then w:=w+c div pp
                       else w:=w-c div pp;
            if q=lv then ok:=false;
         end;
         ver:=w;
    end;

function cauta(a,b:int64): longint;
      var t:int64;
      begin

        if a=b then t:=a
           else
            begin
              c:=(a+b) div 2;
              m:=ver(c);
              if (m=p) and (prime(n,c))
                 then t:=c else
              if m>=p then t:=cauta(a,c)
                           else  t:=cauta(c+1,b);            end;
       cauta:=t;
      end;
begin
assign(f,'frac.in');
reset(f);
readln(f,n,p);
close(f);
m:=n;
lv:=0;
if n mod 2=0 then begin
         inc(lv);
         v[lv]:=2; while n mod 2=0 do n:=n div 2;end;
i:=3;
while (n<>1)and(i<=n) do
   begin
      if n mod i=0 then begin inc(lv); v[lv]:=i; while n mod i=0 do n:=n div i;end;
      inc(i,2);
   end;
n:=m;
assign(g,'frac.out');
rewrite(g);
writeln(g,cauta(0,1000000000));
close(g);
end.