var a:array[0..1000,0..1000]of integer;
    b:array[1..500]of integer;
    c:array[0..1,1..1000,0..500]of integer;
    n,i,j,dm,i1,i2,z,l:integer;
    r:longint;

begin
  for i:=1 to 1000 do
     begin
       a[i,0]:=i;
       for j:=1 to i do
         begin
           a[i,j]:=a[j,i mod j];
         end;
     end;
  assign(input,'indep.in'); reset(input);
  readln(n);
  for i:=1 to n do readln(b[i]);
  c[1,b[1],0]:=1; c[1,b[1],1]:=1; i1:=1; i2:=0;
  for i:=2 to n do
    begin
      i1:=i2; i2:=(i2+1)and 1;
      c[i1,b[i],0]:=1; c[i1,b[i],1]:=1;
      for j:=1 to 1000 do
        begin
          dm:=a[b[i],j]; if dm=0 then dm:=a[j,b[i]];
          for z:=1 to c[i2,j,0] do
            begin
              c[i1,dm,z]:=c[i1,dm,z]+c[i2,j,z]+r; r:=0;
              if c[i1,dm,z]>9 then begin r:=c[i1,dm,z]div 10; c[i1,dm,z]:=c[i1,dm,z]mod 10; end;
            end;
          l:=c[i2,j,0];
          while r<>0 do begin inc(l); c[i1,dm,l]:=c[i1,dm,l]+r; r:=0; if c[i1,dm,l]>9 then begin r:=c[i1,dm,l]div 10; c[i1,dm,l]:=c[i1,dm,l]mod 10; end;  end;
          if l>c[i1,dm,0] then c[i1,dm,0]:=l;
          for z:=1 to c[i2,j,0] do
            begin
              c[i1,j,z]:=c[i1,j,z]+c[i2,j,z]+r;
              c[i2,j,z]:=0;
              r:=0;
              if c[i1,j,z]>9 then begin r:=c[i1,j,z]div 10; c[i1,j,z]:=c[i1,j,z]mod 10; end;
            end;
          l:=c[i2,j,0]; c[i2,j,0]:=0;
          while r<>0 do begin inc(l); c[i1,j,l]:=c[i1,j,l]+r; r:=0; if c[i1,j,l]>9 then begin r:=c[i1,j,l]div 10; c[i1,j,l]:=c[i1,j,l]mod 10; end; end;
          if l>c[i1,j,0] then c[i1,j,0]:=l;
        end;
    end;
  assign(output,'indep.out'); rewrite(output);
  if n and 1 =1 then n:=1 else n:=0;
  for i:=c[n,1,0] downto 1 do write(c[n,1,i]);
  close(output);
end.