#include <bits/stdc++.h>
#define ll long long
#define LL long long
#define ls p<<1
#define rs p<<1|1
#define Ma 30005
#define mod 998244353
#define PLL pair<ll,ll>
#define PDD pair<double,double>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fi first
#define se second
#define N 16
#define pb push_back
#define ld long double
#define all(x) x.begin(),x.end()
#define inf 1e18

using namespace std;
ll n,m,k;
ll a[Ma];
ll p[16]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};//16
//53*59

struct node{
	vector <ll> v;
	ll col,x;
	bool operator <(const node &A)const{
		return v.back()<A.v.back();
	}
	bool operator !=(const node &A)const{
		return v.back()!=A.v.back();
	}
}T[Ma];


ll po(ll p,ll x=mod-2)
{
	ll sum=1;
	while (x)
	{
		if (x&1) sum=(LL)sum*p%mod;
		p=(LL)p*p%mod;
		x>>=1;
	}
	return sum;
}

ll pw[Ma];

void go(ll x,ll id)
{
	T[id].x=x;
	vector <ll> v;
	ll col=0;
	if (x==1)
	{
		v.pb(1);
		T[id].v=v,T[id].col=col;
		return;
	}
	for (ll i=0;i<N;i++)
	{
		while (x%p[i]==0)
			x/=p[i],v.pb(p[i]),col|=(1<<i);
	}
	if (x!=1)
		v.pb(x);
	T[id].v=v,T[id].col=col;
	return;
}

ll dp[1<<N][2],ne[1<<N][2];


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

void sol()
{
	for (ll i=1;i<Ma;i++)
		pw[i]=po(i);
	cin>>n;
	for (ll i=1;i<=n;i++)
	{
		ll x;
		cin>>x;
		go(x,i);		
	}
	sort(T+1,T+n);
	dp[0][0]=1;
	for (ll i=1;i<=n;i++)
	{
		if (i>1&&T[i]!=T[i-1])
		{
			for (ll j=0;j<(1<<N);j++)
				add(dp[j][0],dp[j][1]),dp[j][1]=0;
		}
		for (ll j=0;j<(1<<N);j++)
			ne[j][0]=dp[j][0],ne[j][1]=dp[j][1];
		for (ll j=0;j<(1<<N);j++)
		{
			ll res0=T[i].x;
			ll np=(j|T[i].col);
			ll res1=res0;
			if (T[i].v.back()>p[N-1])
				res1=(LL)res1*(T[i].v.back()-1)%mod*po(T[i].back())%mod;
			add(ne[np][1],((LL)dp[j][0]*res1+(LL)dp[j][1]*res0)%mod);
		}
		swap(ne,dp);
	}
	ll res=0;
	for (ll i=0;i<(1<<N);i++)
	{
		ll ad=(dp[i][0]+dp[i][1])%mod;
		for (ll j=0;j<N;j++)
			if (i>>j&1)
				ad=ad*(p[j]-1)%mod*po(p[j])%mod;
		add(res,ad);
	}
	printf("%lld\n",res);
	return;
}

int main()
{
	IOS
	ll tt=1;
	//cin>>tt;
	while (tt--)
		sol();
	return 0;
}


/*
3
1 2 3

2
71 67

*/

answer.code: In function ‘void sol()’:
answer.code:109:77: error: ‘struct node’ has no member named ‘back’
  109 |                                 res1=(LL)res1*(T[i].v.back()-1)%mod*po(T[i].back())%mod;
      |                                                                             ^~~~