考慮初始的答案，顯然為卡特蘭數(shù) \(H(n)\)。

考慮加入一對(duì)括號(hào) \((l,r)\) 時(shí)對(duì)答案的貢獻(xiàn)。（\((l,r)\) 表示有一對(duì)括號(hào)，左括號(hào)在 \(l\)，右括號(hào)在 \(r\)。）

我們默認(rèn)一開(kāi)始有一對(duì)括號(hào) \((0,n+1)\)。當(dāng)出現(xiàn)一對(duì)括號(hào) \((l,r)\) 時(shí)，首先要加上 \((l,r)\) 中的貢獻(xiàn)，然后最小的包含了 \((l,r)\) 的括號(hào)要減去 \((l,r)\) 之間的貢獻(xiàn)。具體地，可以用 \(hp_i\) 表示以 \(i\) 為右括號(hào)的括號(hào)中還有多少個(gè)空位，則這一對(duì)括號(hào)的貢獻(xiàn)即為 \(H(hp_i)\)。預(yù)處理卡特蘭數(shù)，時(shí)間復(fù)雜度為 \(O(n^2)\)。

#include<cstdio>
#include<iostream>
#include<stack>
#define ll long long
#define il inline

using namespace std;
namespace asbt{
namespace cplx{bool begin;}
const int maxn=5e3+5,mod=998244353;
il int qpow(int x,int y){
	int res=1;
	while(y){
		if(y&1){
			res=res*1ll*x%mod;
		}
		x=x*1ll*x%mod,y>>=1;
	}
	return res;
}
namespace cplx{
	bool end;
	il double usdmem(){return (&begin-&end)/1048576.0;}
}
int main(){
	ios::sync_with_stdio(0),cin.tie(0);
	int T,*fac=new int[maxn](),*inv=new int[maxn]();
	fac[0]=fac[1]=1;
	for(int i=2;i<=5e3;i++){
		for(int j=1;j<=i;j++){
			(fac[i]+=fac[j-1]*1ll*fac[i-j]%mod)%=mod;
		}
	}
//	for(int i=0;i<=5e3;i++){
//		cout<<fac[i]<<" ";
//	}
//	puts("");
	for(int i=0;i<=5e3;i++){
		inv[i]=qpow(fac[i],mod-2);
	}
//	for(int i=0;i<=5e3;i++){
//		cout<<fac[i]*1ll*inv[i]%mod<<" ";
//	}
//	puts("");
	cin>>T;
	while(T--){
		int n;
		cin>>n;
		int *hp=new int[n*2+5](),*f=new int[n*2+5]();
		hp[n<<1|1]=n,f[n<<1|1]=-1;
		int ans=fac[n];
		cout<<ans<<" ";
		for(int i=1,l,r,tot;i<=n;i++){
			cin>>l>>r;
			f[l]=1,f[r]=-1;
			tot=r-l-1;
			stack<int> zhan;
			for(int j=l+1;j<r;j++){
				if(f[j]==1){
					zhan.push(j);
				}
				else if(f[j]==-1){
					int tmp=zhan.top();
					zhan.pop();
					if(zhan.empty()){
						tot-=j-tmp+1;
					}
				}
			}
//			cout<<tot<<"\n";
			tot>>=1;
			ans=ans*1ll*fac[tot]%mod;
			hp[r]=tot;
			for(int j=r+1;j<=(n<<1|1);j++){
				if(f[j]==1){
					zhan.push(j);
				}
				else if(f[j]==-1){
					if(zhan.empty()){
						ans=ans*1ll*inv[hp[j]]%mod;
						hp[j]-=tot+1;
						ans=ans*1ll*fac[hp[j]]%mod;
						break;
					}
					else{
						zhan.pop();
					}
				}
			}
			cout<<ans<<" ";
		}
		cout<<"\n";
		delete[] hp,f;
	}
	delete[] fac,inv;
	return 0;
}
}
int main(){return asbt::main();}