import math 
N = int(input())
A = list(map(int,input().split()))
FH = []
SH = []
ans = 0
for i in range(N):
    if i%2==0:
        FH.append(A[i])
    else:
        SH.append(A[i])
FHL = [0]
SHL = [0]
for fh in FH:
    temp = len(FHL)
    for j in range(temp):
        FHL.append(math.gcd(FHL[j],fh))

for sh in SH:
    temp = len(SHL)
    for j in range(temp):
        SHL.append(math.gcd(SHL[j],sh))

for f in FHL:
    for s in SHL:
        if not (f==0 and s==0) and math.gcd(f,s)==1:
            ans+=1
print(ans)