// F - L1-6 邻和

#include <bits/stdc++.h>
#define int long long
#define db double
#define endl "\n"

using namespace std;

void solve() {

    int n;
    cin >> n;
    int ans = 0;
    vector<int> v(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
        if (v[i] == 1) {
            ans++;
            v[i] = lcm(v[i - 1], v[i + 1]);
        }
    }

    vector<int> all(n);
    for (int i = 1; i < n; i++) {
        all[i] = gcd(v[i], v[i + 1]);
    }
    int sum = 0;
    vector<int> res;
    for (int i = 1; i < n; i++) {
        if (all[i] == 1) {
            sum++;
        } else {
            res.push_back(sum);
            sum = 0;
        }
    }
    res.push_back(sum);

    for (auto it : res) {
        ans += (it + 2 - 1) / 2;
    }
    cout << ans << endl;

    
}

signed main() {

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

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

这题的数据似乎不存在末尾为1的数据，可以用这个代码通过，如果末尾有1的话代码第20行会因为vector的空间开错导致索引越界