The key is represented by an array of n integers, where the i^th integer is denoted by key[i]. The vulnerability factor of the array (key) is defined as the maximum length of a subarray that has a Greatest Common Divisor (GCD) greater than 1.

You are allowed to make a maximum of maxChange modifications to the array, where each modification consists of changing one element in the array to any other value.

Given an integer array key and an integer maxChange, find the least possible vulnerability factor of the key after making at most maxChange changes.

Note: The length of an empty subarray is considered to be zero.

Example

key = [2, 2, 4, 9, 6]
maxChange = 1

The length of key, n = 5. Here are some possible changes to make:

1. Change the first element to 3. The array becomes key = [3, 2, 4, 9, 6]. The length of the longest subarray with a GCD greater than 1 is 2 for the subarrays [2, 4] and [9, 6].
2. Change the third element of the array to 5. The array becomes key = [2, 2, 5, 9, 6]. In this case, the length of the longest subarray with a GCD greater than 1 is 2 for the subarrays [2, 2] and [9, 6].

Since no operation can reduce the maximum length of any subarray with a GCD greater than 1 to less than 2, the vulnerability factor of the key is 2.

Function Description

Complete the function findVulnerabilityFactor in the editor below.

findVulnerabilityFactor has the following parameters:

• int key[n]: the original encryption key
• int maxChange: the maximum number of elements that can be changed

Returns

• int: the least possible vulnerability factor of the key

Required Method Signature (no stdin/stdout)

int findVulnerabilityFactor(int[] key, int maxChange)

Additional Examples

Additional Example 1

key = [2, 4, 6, 8]
maxChange = 1

Output: 2

With one change, you can break the long even segment, but you cannot eliminate all adjacent even pairs. The minimum possible longest subarray with GCD > 1 has length 2.

Additional Example 2

key = [6, 10, 15]
maxChange = 1

Output: 1

Change the middle value (e.g., to 7) so no length-2 subarray has GCD > 1. Single-element subarrays like [6] still have GCD > 1, so the best possible vulnerability factor is 1.

Additional Example 3

key = [2, 2, 2]
maxChange = 3

Output: 0

Change all elements to 1. Then no subarray has GCD greater than 1, so the maximum length is the empty subarray length 0.