program divk;
const max=1000000;
 var n,k,i,j,t:longint;
     b:array [1..1000000] of byte;
     a:array [0..1000000,0..8] of longint;
     b1,b2:array [1..1 shl 15] of char;
     fi, fo:text;
begin
 assign(fi,'divprim.in');
 assign(fo,'divprim.out');
 settextbuf(fi,b1);
 settextbuf(fo,b2);
  reset(fi);
  rewrite(fo);
 readln(fi,t);
 for i:=2 to max do
  if b[i]=0 then begin
    b[i]:=1;
   for j:=2 to max div i do
                          inc(b[i*j]);
    end;
 for i:=1 to max do begin
    a[i]:=a[i-1];
   if b[i]<=7 then a[i,b[i]]:=i;
      end;
 for i:=1 to t do begin
   readln(fi,n,k);
    writeln(fo,a[n,k]);
     end;
 close(fo);
end.