Strong Elements

#include<bits/stdc++.h>

#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds; // find_by_order, order_of_key

#define ll long long
#define pb push_back
#define all(_obj) _obj.begin(), _obj.end()
#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
const int N = 1e5 + 11, mod = 1e9 + 7;
ll arr[N];
ll max(ll a, ll b) { return ((a > b) ? a : b); }
ll min(ll a, ll b) { return ((a > b) ? b : a); }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void sol(void)
{
    ll n; cin >> n;
    ll v[n];
    for (ll i = 0; i < n; ++i)
    {
        cin >> v[i];        
    }
    if(n==1) {
        cout<<1<<"\n";
        return;
    }
    vll pre(n), suf(n);
    pre[0]=v[0], suf[n-1]=v[n-1];
    for(int i=1;i<n;i++){
        pre[i] = __gcd(pre[i-1], v[i]);
    }
    for(int i=n-2;i>=0;i--){
        suf[i] = __gcd(suf[i+1], v[i]);
    }
    ll cnt = 0;
    for (int i = 0; i <= n-1; ++i)
    {
        if(i==0)
        {
            if (suf[i+1] != 1)
            {
                cnt++;
                continue;
            }
        }
        if(i==n-1)
        {
            if (pre[i-1] != 1)
            {
                cnt++;
                continue;
            }
        }
        if (__gcd(pre[i-1],suf[i+1]) != 1) cnt++;
    }
    cout << cnt << endl;
    
    return;
    
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    int test;
    cin >> test;
    while (test--)
        sol();
}