var f,g:Text;
    a:array[0..10,0..1000010]of byte;
    v:array[0..1000010]of longint;
    t,i,j,n,k,ok:longint;
begin
assign(f,'divprim.in');
assign(g,'divprim.out');
reset(f);
rewrite(G);
read(f,t);
for i:=1 to 500000 do
  v[i*2]:=1;
i:=3;
while (i<1000000) do
  begin
    if (v[i]=0)then
      for j:=1 to 1000000 div i do
        inc(v[i*j]);
    inc(i,2);
  end;
for i:=2 to 1000000 do
  a[v[i],i]:=1;
for i:=1 to t do
  begin
    read(f,n,k);
    if (k=0)then writeln(g,1)else
    begin
      ok:=0;
      for j:=n downto 1 do
        if (a[k,j]=1)then
          begin
            ok:=1;
            break;
          end;
      if (ok=1)then writeln(g,j)else writeln(g,0);
    end;
  end;
close(F);
close(g);
end.