#include<bits/stdc++.h> using namespace std; #define int long long #define pii pair<int,int> #define fr first #define sc second const int MAXN=1000010,N=20,Mod=998244353; int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x*f;} int n,a[MAXN],p[MAXN],t[MAXN],s[MAXN],cnt; int isp[MAXN]; vector<int>st[MAXN]; void zsx(int x){ for(int i=2;i<=x;i++){ if(!isp[i]){ p[++cnt]=i; isp[i]=cnt; } for(int j=1;j<=cnt&&p[j]*i<=x;j++){ isp[p[j]*i]=1; if(i%p[j]==0)break; } } } int gcd(int x,int y){ return !x||!y?x|y:gcd(y%x,x); } void slv(){ n=read(); for(int i=1;i<=cnt;i++){ st[i].clear();t[i]=s[i]=0; } for(int i=1;i<=n;i++){ a[i]=read(); for(int j=1;p[j]*p[j]<=a[i];j++){ if(a[i]%p[j]==0){ int tmp=1; while(a[i]%p[j]==0){ tmp*=p[j]; a[i]/=p[j]; } st[j].push_back(tmp); } } if(a[i]!=1){ st[isp[a[i]]].push_back(a[i]); } } int bg=0,lst=0; for(int i=1;i<=cnt;i++){ if(!st[i].empty()){ sort(st[i].begin(),st[i].end()); if(!bg)bg=i; t[i]=lst,s[lst]=i,lst=i; } } int ans=0,tot=0; while(bg){tot++; int tmp=1; for(int i=bg;i;i=s[i]){ tmp=tmp*st[i][st[i].size()-1]%Mod; st[i].pop_back(); if(st[i].empty()){ if(i==bg)bg=s[i]; s[t[i]]=s[i]; t[s[i]]=t[i]; } } ans=(ans+tmp)%Mod; } if(tot<n)ans=(ans+n-tot)%Mod; printf("%lld\n",ans); } signed main(){ zsx(1000000); int _=read();while(_--) slv(); return 0; }