program divprim;
var n,k,x,i,j,c,t,l : longint;
    v:array[1..1000000] of longint;
    stop:boolean;
    f,g:text;
 begin
  assign(f,'divprim.in');
  assign(g,'divprim.out');
  reset(f);
  rewrite(g);
  readln(f,t);
  for l:=1 to t do
  begin
  read(f,n);
  readln(f,k);
  stop:=false;
  c:=0;
  for i:=2 to n do
   v[i]:=0;
  for i:=2 to n div 2 do
   for j:=2 to n div i do
    v[i*j]:=1;
  i:=n;
  while (i>=1) and not stop do
  begin
   for j:=2 to n div 2 do
    if (i mod j=0) and (v[j]=0) then
      c:=c+1;
    if c=k then
    stop:=true
    else
    c:=0;
    i:=i-1;
   end;
  if stop then
  begin
   x:=i+1;
   writeln(g,x);
  end
  else writeln(g,0);
  end;
   close(f);
   close(g);
 end.