from math import gcd
from collections import defaultdict

def findVulnerabilityFactor(key, maxChange):
    from math import gcd
    from functools import lru_cache

    n = len(key)

    # Helper: Compute GCD of subarray from l to r
    def subarray_gcd(arr):
        g = arr[0]
        for num in arr[1:]:
            g = gcd(g, num)
            if g == 1:
                return 1
        return g

    # Check if it's possible to make all subarrays of length > L have GCD == 1
    def is_valid(L):
        for i in range(n):
            g = 0
            cnt = 0
            for j in range(i, n):
                g = gcd(g, key[j])
                if g == 1:
                    break
                cnt += 1
                if cnt > L:
                    # Try to break it with at most maxChange changes
                    # Try changing elements to 1 inside window [i..j]
                    # Count how many need to be changed to make GCD 1
                    change_needed = 0
                    for k in range(i, j + 1):
                        if key[k] % g == 0:
                            change_needed += 1
                    if change_needed <= maxChange:
                        continue
                    else:
                        return False
        return True

    # Binary search on the minimum vulnerability factor
    left, right = 0, n
    answer = n
    while left <= right:
        mid = (left + right) // 2
        if is_valid(mid):
            answer = mid
            right = mid - 1
        else:
            left = mid + 1
    return answer

def main():
    # Test Case 1
    key1 = [2, 2, 4, 9, 6]
    maxChange1 = 1
    result1 = findVulnerabilityFactor(key1, maxChange1)
    print(f"Test Case 1: Vulnerability Factor = {result1}")  # Expected: 2

    # Test Case 2
    key2 = [5, 10, 20, 10, 15, 5]
    maxChange2 = 2
    result2 = findVulnerabilityFactor(key2, maxChange2)
    print(f"Test Case 2: Vulnerability Factor = {result2}")  # Expected: 2

if __name__ == "__main__":
    main()