$dp[i][j]$,考虑前$i$个，最小公倍数为$j$的最大个数

不会计算第二维的个数，不过这份代码ac了，正确性可以证明吗？

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

#define int long long
#define endl '\n'

int a[200005], b[200005];
map<int,int> dp[2005];

void solve(){

    int n;
    cin>>n;

    map<int,int> mp;
    for(int i=1;i<=n;i++) cin>>a[i], dp[i].clear(), mp[a[i]] = 1;
    sort(a+1,a+1+n);

    int z = 1;
    for(int i=1;i<=n;i++){
        z = z/__gcd(z,a[i])*a[i];
        if(z>a[n]){
            cout<<n<<endl;
            return ;
        }
    }
    
    dp[0][1] = 0;
    int ans = 0;
    for(int i=1;i<=n;i++){
        for(auto [x,y] : dp[i-1]){
            dp[i][x] = y;
        }
        for(auto [x,y] : dp[i-1]){
            z = x/__gcd(x,a[i])*a[i];
            dp[i][z] = max(dp[i][z],y+1);
            if(!mp.count(z)) ans = max(ans,dp[i][z]);
        }
    }
    cout<<ans<<endl;

}
signed main() {

    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int T;
    cin>>T;
    while(T--){
        solve();
    }

    return 0;
}