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:=2 to c div i do v[i*j]:=1;
end;

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

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