#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<pair<pii, vector<int>>> 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;
}
#define ull unsigned long long
int &mul(int &x, int y)
{
    ull c = (ull)x * y - (ull)((long double)x / mod * y + 0.5L) * mod;
    if (c >= mod)
        x = c + mod;
    else
        x = c;
    return x;
}
/*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 = 1e5 + 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];

    set<int> st;
    vector<int> cnt(16);
    for (auto x : a)
    {
        int s = 0;
        for (int i = 0; i < 16; i++)
        {
            cnt[i] = 0;
        }
        int fac = MaxFac(x, s, cnt);
        vec[fac].push_back(mp(mp(x, s), cnt));
        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 [tmp, xcnt] : vec[y])
        {
            auto [x, xs] = tmp;
            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 & (1ll << j))
                        mul(val, P[j] - 1);
                    if (sec & (1ll << j))
                        mul(val, P[j]);
                    // val = val*Pow(P[j], xcnt[j]-1);
                    if (xcnt[j] - 1 >= 1)
                        mul(val, Pow[j][xcnt[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;
}