var f,g:text;
    i,j,t,n,k:longint;
    v:array[1..1000000] of byte;
procedure init;
begin
 v[1]:=0;
 for i:=2 to 1000000 do
 v[i]:=0;
end;
procedure e{ratostene};
var i,j:longint;
begin
 for i:= 2 to 1000000 do
  if v[i]=0 then
   begin
    v[i]:=1;
    j:= i+i;
    while j<=1000000 do
     begin
      if v[j]<7 then
       v[j]:=v[j]+1;
      j:=j+i;
     end;
   end;
end;
procedure load;
var i,j:longint;
begin
 assign(f,'divprim.in');reset(f);
 assign(g,'divprim.out');rewrite(g);
 readln(f,t);
 for i:=1 to t do
  begin
  readln(f,n,k);
   j:=n;
   while (v[j]<>k) and (j>1) do
   j:=j-1;
   if j>1 then
   writeln(g,j)
   else
   writeln(g,0)
  end;
end;

BEGIN
init;
e;
load;

writeln(i);
close(f);close(g);

END.