//20pts #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,base=59,mod=998244353,base2=1145141,mod2=1011451423; 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,a[maxn],fa[maxn],mx[maxn],mn[maxn],Pow[maxn],Pow2[maxn],dt[maxn],CT;pi hsh[maxn]; bool vis[maxn]; 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; } int find(int x){ if(fa[x]==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; fa[x]=y;CT--; mx[y]=max(mx[y],mx[x]),mn[y]=min(mn[y],mn[x]); } pi qry(int l,int r){ int h1=hsh[r].p1,h2=hsh[r].p2; h1-=hsh[l-1].p1*1ll*Pow[r-l+1]%mod; if(h1<0)h1+=mod; h2-=hsh[l-1].p2*1ll*Pow2[r-l+1]%mod2; if(h2<0)h2+=mod2; return m_p(h1,h2); } void slv(){ n=read();up(i,1,n)a[i]=read();CT=n; bool qwq=1,testC=1; up(i,1,n)testC&=(a[i]<=2); up(i,1,n)fa[i]=i,mx[i]=read(),mn[i]=read(),qwq&=(mn[i]==mx[i]); if(qwq){ set<int>s; up(i,1,n)s.insert(mx[i]); if(s.size()==1){ up(k,1,n/2)printf("1 ");printf("\n"); return; } } Pow[0]=Pow2[0]=1; up(i,1,n)Pow[i]=Pow[i-1]*1ll*base%mod,Pow2[i]=Pow2[i-1]*1ll*base2%mod2; up(i,1,n)hsh[i].p1=(hsh[i-1].p1*1ll*base%mod+a[i])%mod,hsh[i].p2=(hsh[i-1].p2*1ll*base2%mod2+a[i])%mod2; ll lst=0; up(k,1,n/2){ if(testC&&k>80){ printf("%d ",lst); continue; } if(CT==1){ int w=mx[find(1)]-mn[find(1)]+1; up(kk,k,n/2)printf("%d ",w); printf("\n");return; } up(i,1,n)dt[i]=0; up(i,1,n-2*k+1)if(qry(i,i+k-1)==qry(i+k,i+2*k-1))dt[i]++,dt[i+k]--; up(i,1,n){ dt[i]+=dt[i-1]; if(dt[i])mg(i,i+k); }ll res=1;bool ff=1; up(i,1,n){ int x=find(i); if(vis[x])continue; if(mx[x]>mn[x]){ ff=0;break; }vis[x]=1; res=res*1ll*(mn[x]-mx[x]+1)%mod; }if(!ff){ up(kk,k,n/2)printf("0 "); printf("\n");return; }printf("%d ",lst=res); up(i,1,n)vis[find(i)]=0; }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; }