#include<bits/stdc++.h> #define int long long #define pii pair<int,int> #define mkp make_pair #define fi first #define se second #define push_back emplace_back using namespace std; const int mod=998244353; const int maxn=1e6+7; int tg[maxn]; int p[maxn],cnt; int minp[maxn]; void init(int n){ tg[1]=1,cnt=0; for(int i=2;i<=n;i++){ if(!tg[i])p[++cnt]=i,minp[i]=i; for(int j=1;j<=cnt;j++){ if(i*p[j]>n)break; tg[i*p[j]]=1,minp[i*p[j]]=min(minp[i],p[j]); if(i%p[j]==0)break; } } } inline int qpow(int a,int b){ int ans=1; while(b){ if(b&1)ans=ans*a%mod; a=a*a%mod; b>>=1; } return ans; } int n; int a[maxn]; set<int> s; vector<pair<int,int> > v[maxn]; void slv(){ for(auto it=s.begin();it!=s.end();it++)v[*it].clear(); s.clear(); // cout<<"CLR"<<endl; int ans=0; cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; for(int i=1;i<=n;i++){ int x=a[i]; while(x>1){ int p=minp[x]; int tot=0; int pw=1; while(x%p==0)tot++,x/=p,pw=pw*p%mod; v[p].push_back(tot,pw); s.insert(p); } } for(auto it=s.begin();it!=s.end();it++)sort(v[*it].begin(),v[*it].end()); for(int i=1;i<=n;i++){ int cur=1; for(auto it=s.begin();it!=s.end();){ cur=cur*v[*it].back().se%mod; v[*it].pop_back(); if(v[*it].empty())it=s.erase(it); else it++; } ans=(ans+cur)%mod; } cout<<ans<<endl; } void MT(){ int t; cin>>t; while(t--)slv(); } signed main(){ init(maxn-1); MT(); }