const c=1000000;
type vector=array [1..c] of integer;

procedure eratostene(var v:vector);
var i,j:longint;
begin
 for i:=2 to c do
  if v[i]=0 then
   for j:=1 to c div i do inc(v[i*j]);
end;

var t,n,k,i,j:longint;
    v:vector;
begin
 assign(input,'divprim.in');reset(input);
 assign(output,'divprim.out');rewrite(output);
  eratostene(v); readln(t);
  for i:=1 to t do begin
   readln(n,k);
   for j:=n downto 0 do begin
    if k=v[j] then begin
     writeln(j); break;
    end;
   end;
   if j=0 then writeln(0);
  end;
 close(input);close(output);
end.