var fi,fo:text;
    i,j,n,t,k:longint;
    nrdiv,prim:array[0..1000000]of integer;
    a:array[1..1000000,0..7]of longint;
begin
     assign(fi,'divprim.in'); reset(fi);
     assign(fo,'divprim.out'); rewrite(fo);
     i:=2;
     while i<=1000000 do
        begin

             if prim[i]=0 then
                begin
                     nrdiv[i]:=1;
                     j:=2*i;
                     while j<=1000000 do
                        begin
                             prim[j]:=1;
                             nrdiv[j]:=nrdiv[j]+1;
                             inc(j,i);
                        end;
                end;
             inc(i);
        end;
     for i:=0 to 7 do
        begin
             for j:=1 to 1000000 do
                begin
                     if nrdiv[j]=i then a[j,i]:=j
                                   else a[j,i]:=a[j-1,i];
                end;
        end;
     readln(fi,t);
     for i:=1 to t do
        begin
             read(fi,n,k);
             {for j:=n downto 1 do begin
                if nrdiv[j]=k then begin writeln(fo,j); break; end;
                if j=1 then writeln(fo,'0');
             end;}
             writeln(fo,a[n,k]);
        end;
     close(fi);
     close(fo);
end.