#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define p_b push_back #define m_p make_pair #define pi pair<int,int> #define p1 first #define p2 second using namespace std; typedef long long ll; const int maxn=1e6+10,base1=20100417,mod1=1011451423,base2=1145141,mod2=998244853; const int mod=998244353; inline ll read(){ ll x=0;short t=1; char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')t=-1;ch=getchar(); }while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; }int n,s[maxn],Pow1[maxn],Pow2[maxn],Log2[maxn]; pi hsh[maxn]; ll res; int qpow(int a,int b){ int res=1; while(b){ if(b&1)res=res*1ll*a%mod; a=a*1ll*a%mod;b>>=1; }return res; } struct dsu { int fa[maxn],siz[maxn]; void init(){ up(i,1,n)fa[i]=i,siz[i]=1; } int find(int x){ if(x==fa[x])return x; return fa[x]=find(fa[x]); }void mg(int x,int y){ x=find(x),y=find(y); if(x==y)return; if(siz[x]<siz[y])swap(x,y); fa[y]=x,siz[y]+=siz[x]; } }T[21]; struct dsu2 { int fa[maxn],siz[maxn],mx[maxn],mn[maxn]; void init(){ up(i,1,n)fa[i]=i,siz[i]=1; } int find(int x){ if(x==fa[x])return x; return fa[x]=find(fa[x]); }void mg(int x,int y){ x=find(x),y=find(y); if(x==y)return; if(siz[x]<siz[y])swap(x,y); if(mx[x]<=mn[x]&&mx[y]<=mn[y]){ res=res*1ll*qpow(mn[x]-mx[x]+1,mod-2)%mod; res=res*1ll*qpow(mn[y]-mx[y]+1,mod-2)%mod; } fa[y]=x,mx[x]=max(mx[x],mx[y]),mn[x]=min(mn[x],mn[y]); if(mx[x]<=mn[x])res=res*1ll*(mn[x]-mx[x]+1)%mod; else res=0; siz[x]+=siz[y]; } }T2; void mg(int x,int y,int dep){ // cout<<"mg "<<x<<' '<<y<<'\n'; if(T[dep].find(x)==T[dep].find(y))return; T[dep].mg(x,y); if(!dep){ T2.mg(x,y);return; }mg(x,y,dep-1),mg(x+(1<<(dep-1)),y+(1<<(dep-1)),dep-1); } pi qry(int l,int r){ int h1=hsh[r].p1-hsh[l-1].p1*1ll*Pow1[r-l+1]%mod1; if(h1<0)h1+=mod1; int h2=hsh[r].p2-hsh[l-1].p2*1ll*Pow2[r-l+1]%mod2; if(h2<0)h2+=mod2; return m_p(h1,h2); } int getsuf(int x,int y){ if(s[x]!=s[y])return 0; int l=1,r=x+1; while(l+1<r){ int mid=l+r>>1; if(qry(x-mid+1,x)!=qry(y-mid+1,y))r=mid; else l=mid; }return l; } int getpre(int x,int y){ if(s[x]!=s[y])return 0; int l=1,r=n-y+2; while(l+1<r){ int mid=l+r>>1; if(qry(x,x+mid-1)!=qry(y,y+mid-1))r=mid; else l=mid; }return l; } void slv(){ n=read(); Pow1[0]=Pow2[0]=1; up(i,1,n)Pow1[i]=Pow1[i-1]*1ll*base1%mod1,Pow2[i]=Pow2[i-1]*1ll*base2%mod2; up(i,1,n)s[i]=read(),hsh[i].p1=(hsh[i-1].p1*1ll*base1+s[i])%mod1,hsh[i].p2=(hsh[i-1].p2*1ll*base2+s[i])%mod2; up(i,2,n)Log2[i]=Log2[i>>1]+1; T2.init();up(i,0,Log2[n])T[i].init();res=1; up(i,1,n){ int l=read(),r=read(); T2.mx[i]=l,T2.mn[i]=r; res=res*1ll*(r-l+1)%mod; }bool C=1; up(i,1,n)C&=(s[i]<=2); up(i,1,n/2){ for(int j=i;j<=n;j+=i){ if(j+i>n)break; // cout<<"test "<<j<<' '<<j+i<<' '<<getsuf(j,j+i)<<'\n'; // cout<<"test "<<j<<' '<<j+i<<' '<<getpre(j,j+i)<<'\n'; int l=j-getsuf(j,j+i)+1; int r=j+getpre(j,j+i)-1; if(l>j||r<j||r-l+1<i)continue; // cout<<"merge "<<l<<' '<<r<<' '<<l+i<<' '<<r+i<<'\n'; int k=Log2[r-l+1]; mg(l,l+i,k),mg(r-(1<<k)+1,r+i-(1<<k)+1,k); }printf("%d ",res); if(C&&i==60){ up(j,i+1,n/2)printf("%d ",res); break; } }printf("\n"); }int main(){ // freopen("yoimiya.in","r",stdin); // freopen("yoimiya.out","w",stdout); int t=read();while(t--)slv(); fclose(stdin); fclose(stdout); return 0; }