#include <bits/stdc++.h> #define ll long long int #define ld long double using namespace std; int gcd(int a, int b) { if (b == 0) return a; else return gcd(b, a % b); } void mainSolve() { int n; cin >> n; vector<int> v(n), pref_gcd(n), suff_gcd(n); for (int i = 0; i < n; i++) cin >> v[i]; int all_gcd = v[0]; pref_gcd[0] = v[0]; suff_gcd[n - 1] = v[n - 1]; for (int i = 1; i < n; i++) all_gcd = gcd(all_gcd, v[i]), pref_gcd[i] = gcd(pref_gcd[i - 1], v[i]); for (int i = n - 2; i >= 0; i--) suff_gcd[i] = gcd(suff_gcd[i + 1], v[i]); int ans = 0; for (int i = 0; i < n; i++) { int curr_gcd; if (i == 0) curr_gcd = suff_gcd[i + 1]; else if (i == n - 1) curr_gcd = pref_gcd[i - 1]; else curr_gcd = gcd(pref_gcd[i - 1], suff_gcd[i + 1]); if (curr_gcd != 1) ++ans; } cout << ans << endl; } int main() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif int t; cin >> t; while (t--) { mainSolve(); } return 0; }