The maximum number of subarrays

Problem Statement

The maximum number of subarrays Problem Description You are given an array A of N positive integers. Choose as many subarrays of A as possible so that: every chosen subarray is non-empty, no two chosen subarrays share an element (they do not overlap), and the greatest common divisor (GCD) of all elements of each chosen subarray is exactly 1 . Print the largest number of subarrays you can choose. Elements that are not covered by any chosen subarray are allowed. A subarray is a contiguous part of the array: A[i], A[i+1], ..., A[j] for some 1 <= i <= j <= N (1-based indexing). The GCD of a group of integers is the largest positive integer that divides all of them; for example, gcd(8, 12) = 4 , and the GCD of a single element is the element itself. Complete the function solve(N, A) , which returns the answer for one test case. Input Format The first line contains an integer T , the number of test cases. Each test case consists of two lines: the first contains the integer N , and t