var n,d,t,i,j:longint;
    k:byte;
    v:array[1..1000000]of int64;
begin
assign(input,'divprim.in');reset(input);
assign(output,'divprim.out');rewrite(output);
readln(t);
for i:=2 to 1000000 div 2 do
  if v[i]=0 then
    for d:=2 to 1000000 div i do inc(v[i*d]);
for i:=1 to t do begin
  readln(n,k);
  j:=n;
  while (v[j]<>k)and(j>=2) do
    j:=j-1;
  if j=2 then writeln('0')
    else writeln(j);
end;
close(input);close(output);
end.