#include <bits/stdc++.h>
using namespace std;

#define int long long

void solve() {
    int n;
    cin >> n;

    vector<int> a(n);

    int g = 0;

    for(int i = 0; i < n; i++) {
        cin >> a[i];
        g = __gcd(g, a[i]);
    }

    int cnt = 0;

    for(int x : a) {
        if(x == g) cnt++;
    }

    if(cnt > 0) {
        cout << n - cnt << '\n';
        return;
    }

    int best = 1e9;

    for(int i = 0; i < n; i++) {
        int cur = 0;

        for(int j = i; j < n; j++) {
            cur = __gcd(cur, a[j]);

            if(cur == g) {
                best = min(best, j - i + 1);
                break;
            }
        }
    }

    cout << n + best - 2 << '\n';
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;

    while(t--) solve();
}