Notation and Definitions:

• Let ~n~ be the number of elements in the set ~S~.

• Let ~M~ be the largest element in ~S~.

• Let ~f(X)~ be the number of prime numbers not exceeding ~X~.

Subtask 1: ~M \leq 20~

With this limit, we can iterate through all ~2^n~ possible subsets and check the problem condition directly.

Complexity: ~O(n^2 \times 2^n)~.

Subtask 2: ~M \leq 100~

First, we perform the prime factorization of the elements in ~S~. An important observation is that two numbers ~x~ and ~y~ satisfy ~\gcd(x, y) = 1~ if and only if they have no common prime factors. This allows us to use bitmask dynamic programming to optimize the selection of subsets.

Let ~dp(i, \text{mask})~ be the maximum number of elements that can be selected considering the ~i~-th element, with ~\text{mask}~ representing the set of prime factors that have been used. When considering the element ~s_i~, we can update the state as follows: $$dp(i, \text{mask} \mid \text{bit}(s_i)) = \max[dp(i-1, \text{mask} \mid \text{bit}(s_i)), dp(i-1, \text{mask}) + 1]$$ with the condition: $$\forall i = 1, \dots, n, \quad \forall \text{mask} = 0, \dots, 2^{f(M)} \quad \text{such that } \text{mask} \, \& \, \text{bit}(s_i) = 0.$$ Where ~\text{bit}(s_i)~ is the bit representation of the set of prime factors of ~s_i~.

One point to note is that there may exist some special elements that can be added to any subset while still satisfying the problem condition. Specifically, these are:

• The number ~1~, as it has no prime factors and can always be combined with any other number.

• Prime numbers greater than ~\lfloor \frac{M}{2} \rfloor~, as they cannot have a common factor with any other number in the set (except themselves).

From this, we can infer that we only need to consider prime factors not exceeding ~\lfloor \frac{M}{2} \rfloor~, as prime factors greater than this limit do not affect the validity of the selected subset.

Complexity: ~O(n \times 2^{f(\frac{M}{2})})~.

In practice, when we update ~dp(i, \text{mask})~, we only need to iterate through the subsets of the complement of ~mask~. This significantly reduces the complexity.

Subtask 3: ~M \leq 5000~

With this limit, the approach from subtask 2 becomes infeasible due to the large number of states. To optimize, we divide the set ~S~ into two parts as follows:

• First part: Contains numbers with all prime factors less than or equal to ~\sqrt{M}~.

• Second part: Contains the remaining numbers, i.e., those with the largest prime factor exceeding ~\sqrt{M}~. These numbers can be grouped by their largest prime factor. An important observation is that within each group, we can only select at most one element, as any two numbers in the same group share a common prime factor and cannot both appear in a subset that satisfies the problem condition.

For the first part, we can apply bitmask dynamic programming as in subtask 2, but only considering numbers with prime factors not exceeding ~\sqrt{M}~.

For the second part, we need to adjust the dynamic programming so that each group contributes at most one element to the result set.

Complexity: ~O(n \times 2^{f(\sqrt{M})})~.

We can optimize similarly to Subtask 2. Furthermore, for any group of prime factors that contains a prime number, we can take that prime number and ignore its group of prime factors. .

#include<bits/stdc++.h>
#define endl '\n'
#define fi first
#define se second
using namespace std;
typedef long double ld;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> llll;

int dp[1<<19],dp1[1<<19],fact[5001],a[5001],b[5001],numprime=0,prime[670];
vector<int> v[670];

bool comp(int &a,int &b)
{
    if(fact[a]==fact[b]) return a<b;
    return fact[a]<fact[b];
}

void sieve()
{
    for(int i=1;i<=5000;i++) fact[i]=i;
    for(int i=2;i<=5000;i++)
    {
        if(fact[i]!=i) continue;
        for(int j=i*2;j<=5000;j+=i) fact[j]=i;
    }
    int c=0;
    for(int i=2;i<=67;i++) if(fact[i]==i) b[i]=c++;
    for(int i=67;i<=5000;i++) if(fact[i]==i) prime[numprime++]=i;
}

int tobin(int &temp)
{
    int ans=0;
    while(temp!=1)
    {
        ans|=1<<b[fact[temp]];
        temp/=fact[temp];
    }
    return ans;
}

void solve()
{
    int n,ans=1;
    cin >> n;
    vector<int> liem(n);
    for(int i=0;i<n;i++) cin >> liem[i];
    sort(liem.begin(),liem.end());liem.erase(unique(liem.begin(),liem.end()),liem.end());
    for(int i=1;i<=n;i++) a[i]=liem[i-1];
    sieve();
    sort(a+1,a+1+n,comp);
    int temp=0;
    for(int i=1;i<=n;i++)
    {
        if(fact[a[i]]<=67)
        {
            v[temp].push_back(a[i]);
            continue;
        }
        while(fact[a[i]]>prime[temp]) temp++;
        while(fact[a[i]]>67) a[i]/=fact[a[i]];
        v[temp].push_back(a[i]);
    }
    for(int i=0;i<=temp;i++) sort(v[i].begin(),v[i].end(),comp);
    for(int i=0;i<(int)v[0].size();i++)
    {
        int mask=tobin(v[0][i]);
        int rmask=((1<<19)-1)^mask;
        for(int sub=rmask;;sub=(sub-1)&rmask)
        {
            dp[sub|mask]=max(dp[sub|mask],dp[sub]+1);
            if(!sub) break;
        }
//        for(int j=0;j<(1<<19);j++)
//        {
//            if((mask&j)==0) dp[mask|j]=max(dp[mask|j],dp[j]+1);
//        }
    }
    int ans1=0;
    for(int i=1;i<=temp;i++)
    {
        bool ok=false;
        if(v[i].empty()) continue;
        for(int j=0;j<(int)v[i].size();j++)
        {
            if(ok) break;
            int mask=tobin(v[i][j]);
            if(mask==0)
            {
                ok=true;
                ans1++;
                break;
            }
            int rmask=((1<<19)-1)^mask;
            for(int sub=rmask;;sub=(sub-1)&rmask)
            {
                dp[sub|mask]=max(dp[sub|mask],dp[sub]+1);
                if(!sub) break;
            }
        }
        if(!ok)
        {
            for(int j=0;j<(1<<19);j++)
            {
                if(dp1[j]==0) continue;
                dp[j]=max(dp[j],dp1[j]);
                dp1[j]=0;
            }
        }
    }
    for(int i=0;i<(1<<19);i++) ans=max(ans,dp[i]);
    cout << ans+ans1 << endl;
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    if(fopen("coprime.inp","r"))
    {
        freopen("coprime.inp","r",stdin);
        freopen("coprime.out","w",stdout);
    }
    int t=1;
    //cin >> t;
    while(t--)
    solve();
    return 0;
}