import sys import math def main(): n, *rest = map(int, sys.stdin.read().split()) A = rest[:n] result = 0 current_gcds = {} for num in A: temp_gcds = {} # 添加单独的num if num in temp_gcds: temp_gcds[num] += 1 else: temp_gcds[num] = 1 # 遍历current_gcds中的每个键 for g in current_gcds: new_g = math.gcd(g, num) if new_g in temp_gcds: temp_gcds[new_g] += current_gcds[g] else: temp_gcds[new_g] = current_gcds[g] # 检查是否有GCD为1的情况 if 1 in temp_gcds: result += temp_gcds[1] # 更新current_gcds为temp_gcds current_gcds = temp_gcds.copy() print(result) if __name__ == "__main__": main()