There is an array "val" of n integers. A good subarray is defined as: A subarray val[i to j] is 'good subarray' if gcd(val[i],val[j])>1 (where 0<=i<=j<n).

Task is to split the whole array in such a way that each split subarray is good and one of each element in the array val belongs to exactly one subarray. Calculate the minimum number of splits with each subarray being a 'good subarray'.

Note: gcd(a,b) is greatest commmon divisor of two numbers.

I thought of applying dp but constraints are high. Can anyone help with better approach.