const c=1000000;
type vector=array [1..c+10] 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,aux:longint;
    v:vector;
    v2:array [1..7,1..c+10] of longint;
begin
 assign(input,'divprim.in'); reset(input);
 assign(output,'divprim.out');rewrite(output);
  eratostene(v); readln(t);
  for i:=1 to 7 do
   for j:=1 to c do
    if v[j]=i then begin
     v2[i,j]:=j; aux:=j;
    end
              else v2[i,j]:=aux;
  for i:=1 to t do begin
   readln(n,k);
   if v2[k,n]=1000000 then writeln(0)
                      else writeln(v2[k,n]);
  end;
 close(input); close(output);
end.