The maximum number of subarrays

Problem Statement

The maximum number of subarrays Problem Description You are given an integer array A of size N . Select as many subarrays of A as you can, subject to these conditions: every selected subarray is non-empty (it contains at least one element); every selected subarray is contiguous (it is a block A i , A i+1 , ..., A j with 1 ≤ i ≤ j ≤ N , using 1-based indexing); no two selected subarrays overlap (no index of A belongs to two selected subarrays); the greatest common divisor (GCD) of the elements of every selected subarray is exactly 1 . Print the largest number of subarrays that can be selected at the same time. The GCD of a set of integers is the largest positive integer that divides all of them. For example, gcd(8, 12) = 4 . The GCD of a subarray of one element is that element itself. Input Format The first line contains a single integer T , the number of test cases. Each test case consists of two lines: the first line contains a single integer N , the size of the array; the se