program divp;
var T,l : 1..100000;
    N,i,j,P : 0..1000000;
    K : 0..10;
    f,g : text;
    A,B,C : array [1..1000000] of boolean;

begin
for i := 1 to 1000000 do begin
A[i] := true;
B[i] := false;
end;

for i := 2 to 1000000 do
if A[i] then for j := 2 to 1000000 div i do A[i*j] := false;

assign(f,'divprim.in');
reset(f);
assign(g,'divprim.out');
rewrite(g);

readln(f,T);

for l := 1 to T do begin
readln(f,N,K);


for i := N downto 2 do begin
P := 0;
for j := 2 to (n div 2+1) do begin
if A[j] and (i mod j = 0) then begin
                                inc(P);
                                if P>K then break;
                                end;
end;

if P=K then break
        else P := 0;
end;

if P=K then writeln(g,i)
        else writeln(g,0);

end;

close(f);
close(g);

end.