The maximum number of subarrays

Problem Statement

The maximum number of subarrays Problem Description You are given an integer array A of size N. You have to find the maximum number of non-overlapping subarrays whose size is greater than 0 such that the greatest common divisor of all the subarray equals to 1. The subarray of array A is a contiguous part of array A, that is, arrays A i , A i+1 , ..., A j , for some 1 ≤ i ≤ j ≤ N. Recall, the greatest common divisor (GCD) of two integers, is the largest positive integer that divides each of the integers. For two integers x, y, the greatest common divisor of x and y is denoted as gcd(x, y). For example, the gcd of 8 and 12 is 4, that is, gcd(8, 12) = 4. Note: Assume 1-based indexing of array A. Input format The first line contains an integer T representing the number of test cases. The first line of each test case contains an integer N representing the size of the array. The next line of each test case contains N space-separated integers representing the elements of array A. Out