#include <bits/stdc++.h>
#define ll long long
int a[100],n,dp[61][10001];
ll solve(int index , ll gcd){
    ll ans1,ans2;
    if(index==0)    return 0;
    if(dp[index][gcd])  return dp[index][gcd];
    ans1 = solve(index-1,gcd);
    if(gcd==0){
        ans2=solve(index-1,a[index]);
        ans2+=a[index]==1?1:0;
    }
    else{
        ans2=solve(index-1,__gcd(gcd,(ll)a[index]));
        ans2+=__gcd(gcd,(ll)a[index])==1?1:0;
    }
    dp[index][gcd] = ans1+ans2;
    return ans1 + ans2;
}
int main(){
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    // faster
    int t;
    cin>>t;
    while(t--){
        for(int i=1;i<=60;i++)
            for(int j=0;j<=4000;j++)
                dp[i][j]=0;
        cin>>n;
        f(n)    cin>>a[i+1];
        ll ans = a[n]==1?1:0;
        ans = solve(n-1,a[n]) + solve(n-1,0) ;
        cout<<ans<<"\n";
    }
return 0;
}