#include <bits/stdc++.h> using namespace std; #define int long long #define endl "\n" int L[1000300],R[1000300],f[1000300]; int sz[1000300]; int a[1000300]; int IV[1000300]; int pw1[1000300],pw2[1000300]; int ivpw1[1000300],ivpw2[1000300]; int q,n; inline int ff(int x){return f[x]==x?x:f[x]=ff(f[x]);} const int M=998244353; const int B1=131,B2=31; inline int qp(int a,int x){ int res=1; while(x){ if(x&1)res=res*a%M; a=a*a%M; x>>=1; } return res; } inline int inv(int x){ return qp(x,M-2); } const int IB1=inv(B1),IB2=inv(B2); struct node{ int w1,w2,len; node(int p=0){ w1=w2=p,len=p!=0; } friend node operator +(const node A,const node B){ node C; C.w1=(A.w1+B.w1*pw1[A.len])%M; C.w2=(A.w2+B.w2*pw2[A.len])%M; C.len=A.len+B.len; return C; } friend node operator -(const node A,const node B){ node C; C.len=A.len; C.w1=(A.w1-B.w1+M)%M; C.w2=(A.w2-B.w2+M)%M; return C; } friend bool operator ==(const node A,const node B){ return A.w1==B.w1&&A.w2==B.w2&&A.len==B.len; } inline node shift(int k){ node C; C.w1=w1*ivpw1[k]%M; C.w2=w2*ivpw2[k]%M; C.len=len-k; return C; } }h[1000300]; inline node g(int l,int r){ return (h[r]-h[l-1]).shift(l-1); } int res=1; inline void del(int x){ int len=max(0ll,R[x]-L[x]+1); res=res*IV[len]%M; } inline void ins(int x){ int len=max(0ll,R[x]-L[x]+1); res=res*len%M; } inline void merge(int x,int y){ x=ff(x),y=ff(y); if(x==y)return ; if(sz[x]<sz[y])swap(x,y); del(x),del(y); L[x]=max(L[x],L[y]); R[x]=min(R[x],R[y]); f[y]=x; ins(x); } int fa[21][1000300]; int siz[21][1000300]; inline int ff(int d,int x){ return fa[d][x]==x?x:fa[d][x]=ff(fa[d][x]); } inline void merge(int d,int x,int y){ int fx=ff(d,x),fy=ff(d,y); if(d==0){ merge(x,y); return ; } if(ff(d,x)==ff(d,y))return ; if(siz[d][fx]>siz[d][fy])swap(fx,fy); fa[d][fx]=fy; merge(d-1,x,y),merge(d-1,x+(1<<d-1),y+(1<<d-1)); } int lg[1003000]; inline int mxleft(int m,int k){ int l=1,r=m+1; // cout<<g(m,m).w1<<" "<<g(m,m).w2<<" "<<g(m,m).len<<endl; // cout<<g(m+k,m+k).w1<<" "<<g(m+k,m+k).w2<<" "<<g(m+k,m+k).len<<endl; // cout<<m<<" "<<k<<" "<<(g(m,m)==g(m+k,m+k))<<"!"<<endl; while(l<r){ int mid=l+r>>1; if(g(mid,m)==g(mid+k,m+k))r=mid; else l=mid+1; } return l; } inline int mxright(int m,int k){ int l=m-1,r=n-k; while(l<r){ int mid=l+r+1>>1; if(g(m,mid)==g(m+k,mid+k))l=mid; else r=mid-1; } return l; } signed main(){ ios::sync_with_stdio(0); int t; cin>>t; pw1[0]=1; pw2[0]=1; ivpw1[0]=1; ivpw2[0]=1; for(int i=1;i<=1e6;i++) pw1[i]=pw1[i-1]*B1%M, pw2[i]=pw2[i-1]*B2%M, ivpw1[i]=ivpw1[i-1]*IB1%M, ivpw2[i]=ivpw2[i-1]*IB2%M, IV[i]=inv(i), lg[i]=i==1?0:lg[i>>1]+1; while(t--){ cin>>n; res=1; for(int i=1;i<=n;i++){ cin>>a[i]; h[i]=(h[i-1]+node(a[i])); f[i]=i; } for(int i=20;i>=1;i--) for(int j=1;j<=n;j++) fa[i][j]=j; for(int i=1;i<=n;i++) cin>>L[i]>>R[i],ins(i); for(int k=1;k*2<=n;k++){ for(int i=k;i+k<=n;i+=k){ int l=mxleft(i,k),r=mxright(i,k); // cout<<i<<"x"<<l<<"x"<<r<<" "; if(r-l+1<k)continue; int p=lg[r-l+1]; merge(p,l,l+k); merge(p,r-(1<<p)+1,r-(1<<p)+k+1); i=r; } cout<<res<<" "; } cout<<endl; } cout.flush(); return 0; }