#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define endl '\n'
const int mod=998244353;
int L=(1ll<<16)-1;
int lowbit(int x) {
	return x&(-x);
}
int poww(int a,int b) {
	int res=1;
	while(b) {
		if(b&1) res=1ll*res*a%mod;
		a=1ll*a*a%mod;
		b>>=1;
	}
	return res;
}
int ans[300300],finalans=0,tmp[300300],tmpnex[300300];
void Or(int *a,int type,int n) {
	for(int x=2;x<=n+1;x<<=1) {
		int k=x>>1;
		for(int i=0;i<n+1;i+=x) {
			for(int j=0;j<k;++j) {
				if(i+j+k>n+1) break;
				a[i+j+k]+=(a[i+j]*type+mod)%mod;
				a[i+j+k]%=mod;			
			}
		}
	}
}
int a[3030],n;
int totp=16,p[33]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,52},invp[33];
struct tphi {
	int mxp;
	int s;
	int x;
}node[3030];
tphi solve(int x) {
	tphi res;
	res.s=0;
	res.x=x;
	for(int i=1;i<=totp;++i) {
		if(x%p[i]==0) {
			while(x%p[i]==0) x/=p[i];
			res.s|=1<<(i-1);
		}
	}
	res.mxp=x;
	return res;
}
bool cmp(tphi a,tphi b) {
	return a.mxp<b.mxp;
}
int id[300300];
void gettmp(int l,int r,int mxp) {
	for(int i=0;i<=L;++i) {
		tmp[i]=0;
		tmpnex[i]=0;
	}
	tmp[0]=1;
	for(int i=l;i<=r;++i) {
		int s=node[i].s;
		int x=node[i].x;
		for(int t=0;t<=L;++t) {
			int nt=s|t;
			tmpnex[nt]+=1ll*tmp[t]*x%mod;
			tmpnex[nt]%=mod;
		}
		for(int t=0;t<=L;++t) {
			tmp[t]=(tmp[t]+tmpnex[t])%mod;
			tmpnex[t]=0;
		}
	}
	if(mxp==1) return ;
	int invmxp=poww(mxp,mod-2);
	for(int t=1;t<=L;++t) {
		tmp[t]=1ll*tmp[t]*(mxp-1)%mod*invmxp%mod;
	}
	tmp[0]=1ll*(tmp[0]-1+mod)*(mxp-1)%mod*invmxp%mod;
	tmp[0]=(tmp[0]+1)%mod;
}
signed main() {
	for(int i=1;i<=totp;++i) {
		invp[i]=poww(p[i],mod-2);
		id[poww(2,i-1)]=i;
	}
	scanf("%d",&n);
	for(int i=1;i<=n;++i) {
		scanf("%d",&a[i]);
		node[i]=solve(a[i]);
	}
	sort(node+1,node+n+1,cmp);
	
	ans[0]=1;
	Or(ans,1,L);
	
	for(int l=1,r=1;l<=n;l=r) {
		while((r<=n)&&(node[l].mxp==node[r].mxp)) ++r;
		gettmp(l,r-1,node[l].mxp);
		Or(tmp,1,L);
		for(int t=0;t<=L;++t) {
			ans[t]=1ll*ans[t]*tmp[t]%mod;
		}
	}
	Or(ans,-1,L);
	for(int t=0;t<=L;++t) {
		int x=ans[t];
		for(int s=t;s;s-=lowbit(s)) {
			int i=id[lowbit(s)];
			x=1ll*x*(p[i]-1)%mod*invp[i]%mod;
		}
		finalans=(finalans+x)%mod;
	}
	printf("%d\n",(finalans+mod)%mod);
	return 0;
}

/*
3
1 2 3
*/