program generare_submultimi;
var x,s:array[1..500] of integer;
    i,n,r,nr,cmmdc:integer;f:text;ok:boolean;

function euclid(a,b:integer):integer;
var r:integer;
begin
r:=a mod b;
while r<>0 do begin
      a:=b;
      b:=r;
      r:=a mod b;
      end;
euclid:=b;
end;

procedure solutie;
var k:integer;
begin
ok:=false;
i:=1;k:=1;
while (x[k]<>1)and(k<=n) do inc(k);
cmmdc:=s[k];
for i:=k+1 to n do
    if (x[i]<>0) then cmmdc:=euclid(cmmdc,s[i]);
if cmmdc=1 then ok:=true;
if ok then nr:=nr+1;
end;

procedure bkt(k:integer);
var  i:integer;
begin
if k=n+1 then solutie
else for i:=0 to 1 do begin
         x[k]:=i;
         bkt(k+1);
         end;
end;

procedure citire;
begin
assign(f,'indep.in');reset(f);
readln(f,n);
for i:=1 to n do readln(f,s[i]);
close(f);
end;

procedure scrie;
begin
assign(f,'indep.out');rewrite(f);
writeln(f,nr);
close(f);
end;

begin
citire;
bkt(1);
scrie;
end.