program alex;
var f,g:text;
    p,c: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);
c[1]:=2;
c[2]:=6;
c[3]:=30;
c[4]:=210;
c[5]:=2310;
c[6]:=30030;
c[7]:=510510;
assign(g,'divprim.out');rewrite(g);
for i:=1 to t do
    begin
    readln(f,n,k);
    e:=false;
    if k<=4 then if n-211>c[k] then max:=n-211
                               else max:=c[k]
            else max:=c[k];
    for j:=n downto max 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.