Program cel;
Type stiva=array[1..2] of longint;
     vector=array[1..100000] of longint;
var st:stiva;
    f,g:text;
    a:vector;
    n,k,i,nr,p:longint;
    as,ev:boolean;


function cmmdc(x,y:longint):longint;
Begin
If x mod y=0 then cmmdc:=y
             else cmmdc:=cmmdc(y,x mod y);
end;


procedure init(var st:stiva;k:integer);
Begin
 st[k]:=0;
end;

procedure succesor(var as:boolean;var st:stiva;k:integer);
Begin
If st[k]<n then Begin
                 st[k]:=st[k]+1;
                 as:=true;
                end
           else as:=false;
end;

procedure valid(var ev:boolean;st:stiva;k:integer);
Begin
ev:=true;
If (k>=2) and (a[st[k-1]]=a[st[k]]) then ev:=false;
If (k>=2) and (cmmdc(a[st[k-1]],a[st[k]])<>1) then ev:=false;
p:=cmmdc(a[st[k-1]],a[st[k]])
end;

function solutie(k:longint):boolean;
Begin
solutie:=(k=2);
end;


Begin
Assign(f,'paris.in');Reset(f);
Assign(g,'paris.out');Rewrite(g);
nr:=0;
Readln(f,n);
For i:=1 to n do Readln(f,a[i]);
k:=1;
init(st,k);
While k>0 do
 Begin
  repeat
  succesor(as,st,k);
  If as then valid(ev,st,k);
  until (not as) or (as and ev);
 If as then If solutie(k) then inc(nr)
                          else Begin
                                k:=k+1;
                                init(st,k);
                               end
       else k:=k-1;
 end;
Writeln(g,nr div 2);
end.