var f,g:text;
a:array[2..30000]of integer;
i,n:longint;
q:boolean;
x,y,j,d:integer;
m:2..4;
begin
assign(f,'exp.in');
reset(f);
readln(f,m);
readln(f,n);
for i:=1 to n do
   begin
     read(f,x);
     y:=x;
     for j:=2 to x div 2 do
           if y mod j=0 then
                           while y mod j=0 do
                                begin
                                y:=y div j;
                                a[j]:=a[j]+1;
                                end;
     if y=x then a[x]:=a[x]+1;
   end;
q:=true;
for i:=2 to 30000 do
  if (a[i]<>0) and (a[i] mod m<>0) then q:=false;
assign(g,'exp.out');
rewrite(g);
if q then
  begin
    writeln(g,'1');
    for i:=2 to 30000 do
        if (a[i]<>0) then begin y:=a[i] div m;writeln(g,i,' ',y); end;
    end
  else writeln(g,'0');
close(g);
end.