C

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

#define int long long

signed  main(){
    int t;
    cin>>t;

    while(t--){
        int n;
        cin >> n;
        vector<int> a(n);

        for(auto &e: a) cin>>e;

        int x = 1, f = 0;
        int mx = *max_element(a.begin(),a.end());

        for(int i = 0; i < n; i++){
            x = lcm(x,a[i]);
            if(x > mx){
                cout << n << "\n";
                f = 1 ;
                break;
            }
        }

        if(f)       continue;

        map<int,int> dp, dp2;
        dp[1] = 0;

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

            for(auto [x,y] : dp){
                int val = lcm(x,a[i]);
                dp2[val] = max(dp2[val], y + 1);
            }

            dp = dp2;
        }

        int ans = 0;
        set<int> aa(a.begin(),a.end());

        for(auto [x,y] : dp){
            if(!aa.count(x))
                ans = max(ans,y);
        }

        cout << ans << "\n";
    }
}