import java.util.*; public class Main { public static void main (String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); TreeMap dp = new TreeMap<>(); for (int i = 0; i < n; i++) { int a = sc.nextInt(); HashMap tmp = new HashMap<>(); for (int x : dp.keySet()) { int gcd = getGCD(a, x); if (dp.containsKey(gcd)) { dp.put(gcd, dp.get(gcd) + dp.get(x)); } else { if (tmp.containsKey(gcd)) { tmp.put(gcd, tmp.get(gcd) + dp.get(x)); } else { tmp.put(gcd, dp.get(x)); } } } if (dp.containsKey(a)) { dp.put(a, dp.get(a) + 1); } else { dp.put(a, 1); } for (Map.Entry entry : tmp.entrySet()) { dp.put(entry.getKey(), entry.getValue()); } } if (dp.containsKey(1)) { System.out.println(dp.get(1)); } else { System.out.println(0); } } static int getGCD(int x, int y) { if (x % y == 0) { return y; } else { return getGCD(y, x % y); } } }