#include<bits/stdc++.h>
// #define int long long
using namespace std;
const int N = 3007;
const int mod = 998244353;
int n;
vector<int> P;
bool visP[N];
void InitPrime() {
    visP[1] = 1;
    for(int i=2;i<N;++i) {
        if(!visP[i]) P.push_back(i);
        for(auto p : P) {
            if(p*i >= N) break;
            visP[p * i] = 1;
            if(i%p == 0) break;
        }
    }
}
typedef pair<int,int> pii;
#define mp make_pair
vector<int> xcnt[N];
vector<array<int,3>> vec[N];
int MaxFac(int x,int &s,vector<int> &cnt) {
    for(int i=0;i<16;++i) {
        auto p = P[i];
        if(x%p == 0) s |= (1ll << i);
        while(x%p == 0) x /= p, ++cnt[i];
    }
    return x;
}
const int M = 16;
const int S = (1<<M);
int f[2][S][2];
int& add(int &x,int y) {
    if(x+y>=mod)
    {
        x=x+y-mod;
    }
    else
    {
        x=x+y;
    }
    return x;
}
int& mul(int &x,int y) {
    return x = (long long)x * y % mod;
}
/*int Pow(int x,int y) {
    if(y <= 0) return 1;
    int res = 1, base = x;
    while(y) {
        if(y&1) res = res*base % mod;
        base = base*base % mod;
        y >>= 1;
    }
    return res;
}*/
const int MAXN=4e4+3;
int Pow[16][MAXN];
void InitPow() {
    for(int i=0;i<16;++i) {
        Pow[i][0] = 1;
        for(int j=1;j<MAXN;++j) {
            Pow[i][j] = (long long)Pow[i][j-1] * P[i] % mod;
        }
    }
}
void solve() {
    InitPow();
    cin >> n;
    vector<int> a(n);
    for(int i=0;i<n;++i) cin >> a[i];
    for(int i=0;i<n;i++)
    {
        xcnt[i].resize(16);
    }
    set<int> st;
    for(int i=0;i<n;i++) {
        auto x=a[i];
        int s = 0;
        vector<int> cnt(16, 0);
        int fac = MaxFac(x, s, xcnt[i]);
        vec[fac].push_back({x, s, i});
        st.insert(fac);
    }
    int now = 1, last = 0;
    f[last][0][1] = 1;
    for(auto y : st) {
        for(int s=0;s<S;++s) {
            add(f[last][s][0], f[last][s][1]);
            f[last][s][1] = 0;
        }
        //cout << "test:: " << f[last][0][0] << "\n";
        for(auto [x,xs,id] : vec[y]) {
            
            for(int s=0;s<S;++s) {
                f[now][s][0] = f[last][s][0];
                f[now][s][1] = f[last][s][1];
            }
            for(int s=0;s<S;++s) {
                int fir = xs & (xs^s);
                int sec = xs & (s);
                int val = 1;
                for(int j=0;j<16;++j) {
                    if(!(xs&(1<<j)))continue;
                    if(fir & (1<<j)) mul(val, P[j]-1);
                    if(sec & (1<<j)) mul(val, P[j]);
                    //val = val*Pow(P[j], xcnt[j]-1);
                    if(xcnt[id][j] >= 2) mul(val, Pow[j][xcnt[id][j]-1]);
                    //if((fir & (1ll<<j) )==(sec & (1ll<<j)) && ((fir & (1ll<<j)) == 1)) cout << "wa" << "\n";
                }
                add(f[now][s|xs][1], mul(mul(f[last][s][0], val), max(1, y-1)) );
                add(f[now][s|xs][1], mul(mul(f[last][s][1], val), y) );
            }
            now ^= 1, last ^= 1;
        }
    }
    int ans = 0;
    for(int s=0;s<S;++s) {
        //cout << f[last][s][0] << " " << f[last][s][1] << "\n";
        add(ans, add(f[last][s][0],f[last][s][1]));
    }
    cout << ans << "\n";
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    InitPrime();
    solve();
    return 0;
}