#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define st first
#define nd second
#define mpr make_pair
#define pb push_back
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar())f^=ch=='-';
    for(;isdigit(ch);ch=getchar())x=x*10+(ch^48);
    return f?x:-x;
}
const int S=66005,N=2005,M=3005,mo=998244353,J=54;
inline int qpow(int x,int t){
    int ret=1;
    for(;t;t>>=1,x=x*x%mo)if(t&1)ret=ret*x%mo;
    return ret;
}
inline void red(int &x){x>=mo?x-=mo:0;}
int f[S][2],g[S][2],sym[S],notp[M],n,sprime[20],w[20],m;
pair<int,pii> a[N];
vector<int> prime;
void sieve(){
    notp[1]=1;
    for(int i=2;i<N;++i){
        if(!notp[i])prime.pb(i);
        for(int x:prime){
            if(i*x>=M)break;
            notp[i*x]=1;
        }
    }
    for(int x:prime)if(x<J){
        sprime[m]=x;
        w[m++]=(x-1)*qpow(x,mo-2)%mo;
    }
    for(int i=0;i<(1<<m);++i){
        sym[i]=1;
        for(int j=0;j<m;++j)if(i&(1<<j))
            sym[i]=sym[i]*w[j]%mo;
    }
}
signed main(){
    sieve();
    cout<<m<<endl;
    n=read();
    for(int i=1;i<=n;++i){
        int x=read(),y=0;
        a[i].nd.st=x;
        for(int j=0;j<m;++j)if(x%sprime[j]==0){
            y|=1<<j;
            while(x%sprime[j]==0)x/=sprime[j];
        }
        a[i].st=x;
        a[i].nd.nd=y;
    }
    sort(a+1,a+n+1);
    memset(f,0,sizeof(f));
    memset(g,0,sizeof(g));
    f[0][0]=1;
    auto fk=[&](int r,int x)->int{
        if(r==1)return 1;
        else return r-x;
    };
    for(int l=1,r;l<=n;l=r){
        r=l+1;
        while(r<=n&&a[r].st==a[l].st)++r;
        for(int i=0;i<(1<<m);++i)red(g[i][0]=f[i][0]+f[i][1]);
        for(int i=l;i<r;++i){
            memset(f,0,sizeof(f));
            for(int s=0;s<(1<<m);++s){
                red(f[s][0]+=g[s][0]);
                red(f[s][1]+=g[s][1]);
                int ps=a[i].nd.nd,q,r=a[i].st;
                q=sym[ps^(ps&s)]*a[i].nd.st%mo;
                red(f[s|ps][1]+=g[s][0]*q%mo*fk(r,1)%mo);
                red(f[s|ps][1]+=g[s][1]*q%mo*fk(r,0)%mo);
            }
            memcpy(g,f,sizeof(g));
        }
    }
    int ans=0;
    for(int i=0;i<(1<<m);++i)
        red(ans+=f[i][0]),red(ans+=f[i][1]);
    printf("%lld\n",ans);
}