program alex;
var f,g:text;
    p:array[1..1000000]of longint;
    max,i,t,j,n,k:longint;
    e:boolean;
begin
assign(f,'divprim.in');reset(f);
readln(f,t);
p[1]:=0;
i:=1;
repeat
i:=i+1;
if p[i]=0 then begin
               j:=i+i;
               while(j<=1000000)do
                     begin
                     p[j]:=p[j]+1;
                     j:=j+i;
                     end;
               p[i]:=1;
               end;
until(i>=1000000);
assign(g,'divprim.out');rewrite(g);
for i:=1 to t do
    begin
    readln(f,n,k);
    e:=false;
    for j:=n downto 1 do
        if p[j]=k then begin
                       e:=true;
                       break;
                       end;
    if e=false then writeln(g,0)
               else writeln(g,j);
    end;
close(f);
close(g);
end.