$O(N)$

遍历数组，查看相邻元素是否互质。

• 若互质，则跳过
• 若不互质，设 $a_i$ 与 $a_{i + 1} 不互质，可以修改$a_{i+ 1}$使得$a_{i+ 1}$ 和左右都互质。答案计数加一。

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<LL, LL> PII;

#define x first
#define y second

const int N = 2e5 + 10, M = 60;

int a[N];

void solve()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++)
    {
        cin >> a[i];
    }
    
    int ans = 0;
    for(int i = 1; i < n; i ++)
        if(i < n && __gcd(a[i], a[i + 1]) != 1)
        {
            ans ++;
            i ++;
        }
    cout << ans << endl;
}

int main()
{
    int t = 1;
    cin >> t;
    while(t --)
        solve();
}