var n,i,q,t,j,k,p,c:integer;
    f,g:text;
begin
assign(f,'divprim.in');
assign(g,'divprim.out');
reset(f);
rewrite(g);
readln(f,t);
for i:=1 to t do begin readln(f,n,k);
c:=n;
repeat
c:=c-1;
n:=c;
j:=2;
q:=0;
repeat
p:=0;
while n mod j=0 do begin n:=n div j;  p:=p+1; end;
if p>0 then q:=q+1;
j:=j+1
until n=1;
until (q=k) or (c=1);
if q=k then writeln(g,c)
       else writeln(g,'0');
end;
close(f);
close(g);
end.