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