var n,d,t,i,j,sub,peste:longint;
    k:byte;
    v:array[1..1000000]of longint;
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);
  sub:=n div 2+1;
  peste:=n;
  while (v[sub]<>k)and(sub>0) do sub:=sub-1;
  while (v[peste]<>k)and(peste>=n div 2+1) do peste:=peste-1;
  if (peste<n)and(peste<>sub) then writeln(peste);
  if (peste=n)and(v[n]=k) then writeln(n);
  if (peste=n)and(v[n]<>k)and(sub>0) then writeln(sub);
  if (peste=n)and(v[peste]<>k)and(sub=0) then writeln(0);
end;
close(input);close(output);
end.