#include<bits/stdc++.h>
#define pb push_back
using namespace std;
typedef double db;
typedef long long ll;

const int N=66005,K=2,tot=1<<K;
const ll MOD=998244353;
int n,a[N];
ll f[N],g[N],p[N];
vector<int> ve[N];
int pr[25]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};
ll inv[25];

ll ksm(ll a,ll b)
{
    ll res=1;
    for(int i=b;i;i>>=1,a=a*a%MOD) if(i&1) res=res*a%MOD;
    return res;
}

void work(int a)
{
    int x=a;
    for(int i=0;i<K;i++) if(a%pr[i]==0)
    {
        while(a%pr[i]==0) a/=pr[i];
    }
    ve[a].pb(x);
    //cerr<<' '<<x<<' '<<a<<endl;
}

void input()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),work(a[i]);
}

void add(ll&x,ll y) {x=(x+y)%MOD;}

bool in(int msk,int i) {return (msk>>i)&1;}

int workp(int M)
{
    int nmsk=0,prod=1;
    for(int i=0;i<K;i++)
    {
        int P=pr[i];
        if(M%P) continue;
        nmsk|=(1<<i);
        prod*=P-1,M/=P;
        while(M%P==0) M/=P,prod*=P;
    }
    p[0]=prod;
   // cerr<<'!'<<M<<' '<<p[0]<<endl;
    for(int msk=1;msk<tot;msk++)
    {
        int lb=msk&-msk,j=log2(lb);
        p[msk]=p[msk^lb];
        if(in(nmsk,j)) p[msk]=p[msk]*inv[j]%MOD*pr[j]%MOD;
    }
    //cerr<<' '<<M<<' '<<nmsk<<' '<<p[0]<<' '<<p[1]<<' '<<p[2]<<' '<<p[3]<<endl;
    return nmsk;
}

void dodp(vector<int>ve,int P)
{
    memset(g,0,sizeof(g));
    int Q=P==1?1:P-1;
    for(int M:ve)
    {
        int nmsk=workp(M);
        //cerr<<' '<<nmsk<<endl;
        for(int msk=tot-1;msk>=0;msk--)
        {
            add(g[msk|nmsk],g[msk]*p[msk]%MOD*P%MOD);
            add(g[msk|nmsk],f[msk]*p[msk]*Q%MOD);
            //cerr<<' '<<msk<<' '<<(msk|nmsk)<<' '<<f[msk]<<' '<<p[msk]<<endl;
        }
    }
    // for(int i=0;i<tot;i++)
    // {
    //     cerr<<' '<<i<<" "<<g[i]<<endl;
    // }
    for(int i=0;i<tot;i++) add(f[i],g[i]),g[i]=0;
}

void solve()
{
    input();
    f[0]=1;
    for(int i=1;i<=3000;i++) if(!ve[i].empty()) dodp(ve[i],i);
    ll ans=0;
    for(int i=0;i<tot;i++) add(ans,f[i]);
    printf("%lld\n",ans);
}

void prework()
{
    for(int i=0;i<K;i++) inv[i]=ksm(pr[i]-1,MOD-2);
    // cerr<<' '<<inv[0]<<' '<<inv[1]<<endl;
}

int main()
{
    prework();
    int T=1;
    while(T--) solve();
}