program preoni;
var g,f:text;
n,k,i,j,t:longint;
ok:boolean;
function numar(x:longint):integer;
var i,y,k,nr:longint;
begin
y:=x;
nr:=0;
for i:=2 to y div 2 do
begin
k:=0;
repeat
if x mod i=0 then
begin
inc(k);
x:=x div i;
end;
until x mod i<>0;
if k<>0 then inc(nr);
end;
numar:=nr;
end;
begin
assign(f,'divprim.in');
reset(f);
assign(g,'divprim.out');
rewrite(g);
readln(f,t);
for i:=1 to t do
begin
readln(f,n,k);
ok:=false;
for j:=n downto 2 do
if numar(j)=k then
begin
ok:=true;
break;
end;
if ok then writeln(g,j)
else
writeln(g,0);
end;
close(f);
close(g);
end.