var a:array[1..1000010] of longint;
    c,i,j,k,n,ls,ld,mij:longint;
    t:array[1..7,0..1000000]of longint;

begin
assign(input,'divprim.in');reset(input);
assign(output,'divprim.out');rewrite(output);
a[1]:=0;
for i:=2 to 1000 do
  if(a[i]=0) then
    for j:=1 to 1000000 div i do a[i*j]:=i;

for i:=1001 to 1000000 do
  if a[i]=0 then a[i]:=i;

for i:=2 to 1000000 do begin
  k:=i; while k mod a[i]=0 do k:=k div a[i];
  a[i]:=1+a[k];
end;


for i:=2 to 1000000 do begin
  k:=a[i]; inc(t[k][0]); t[k][t[k][0]]:=i;
end;


readln(c);
for i:=1 to c do begin
  readln(n,k);
  if k=0 then writeln(1)
  else
  if(n<t[k][1]) then writeln(0)
  else begin
    ls:=0; ld:=t[k][0]+1;
    repeat
      mij:=(ls+ld) div 2;
      if t[k][mij]>n then ld:=mij else ls:=mij;
    until ld-ls<=1;
    while(t[k][mij]>n) do dec(mij);
    writeln(t[k][mij]);
  end;
end;
close(input); close(output);
end.