import java.util.*;

public class Main {

    public static int solve(int[] pgcd, int[] sgcd, int skip, int[] nums) {
        int n = nums.length;

        // Prefix GCD
        for (int i = 1; i <= n; i++) {
            if (i - 1 == skip) {
                pgcd[i] = pgcd[i - 1];
                continue;
            }

            pgcd[i] = gcd(pgcd[i - 1], nums[i - 1]);
        }

        // Suffix GCD
        for (int i = n - 1; i >= 0; i--) {
            if (i == skip) {
                sgcd[i] = sgcd[i + 1];
                continue;
            }

            sgcd[i] = gcd(sgcd[i + 1], nums[i]);
        }

        int score = 0;

        for (int i = 0; i < n - 1; i++) {
            if (i == skip) continue;

            if (pgcd[i + 1] == sgcd[i + 1]) {
                score++;
            }
        }

        return score;
    }

    public static int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    public static int maxValidSplits(int[] nums) {
        int n = nums.length;
        int ans = 0;

        int[] premain = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            premain[i] = gcd(premain[i - 1], nums[i - 1]);
        }

        // skip = -1 means no deletion
        for (int i = 0; i <= n; i++) {

            if (i > 0 && premain[i] == premain[i - 1]) {
                continue;
            }

            int skip = i - 1;

            int[] pgcd = new int[n + 1];
            int[] sgcd = new int[n + 1];

            ans = Math.max(
                ans,
                solve(pgcd, sgcd, skip, nums)
            );
        }

        return ans;
    }

    public static void main(String[] args) {

        // Example 1
        int[] nums1 = {10, 30, 15, 10};
        System.out.println(maxValidSplits(nums1)); // 2

        // Example 2
        int[] nums2 = {2, 10, 14};
        System.out.println(maxValidSplits(nums2)); // 1

        // Example 3
        int[] nums3 = {2, 4};
        System.out.println(maxValidSplits(nums3)); // 0
    }
}