#include<bits/stdc++.h>
using namespace std;
typedef unsigned char uc;
typedef long long ll;
#define fi first
#define se second
const int iu=256;
pair<ll,int>f[iu];
ll n,m;
ll pw(ll x,ll y,ll z){
	if(y==0) return 1;
	if(y%2) return x*pw(x,y-1,z)%z;
	ll res=pw(x,y/2,z);
	return res*res%z;
}
ll pwf(ll x,ll y,ll z){
	if(x==0) return 0;
	if(y>=6) return 1;
	ll res=x;
	for(int i=1; i<=y ;i++) res=pw(res,i,z);
	return res;
}
uc w[2][257][iu];
bool c[2][257][iu];
int ff[iu+1],inv[iu+1];
void pre(){
	ff[0]=1;
	for(int i=1; i<=iu ;i++){
		if(i%2==0){
			ff[i]=ff[i-1];continue;
		}
		while(i*inv[i]%iu!=1){
			inv[i]++;
			//cout << i << ' ' << inv[i] << endl;
		}
		ff[i]=ff[i-1]*i%iu;
	}
}
pair<int,int>F(int x){//mod 256
	if(x<2) return {1,0};
	auto duh=F(x/2);
	duh.se+=x/2;
	duh.fi=(duh.fi*ff[x%256])%256;
	return duh;
}
int F2(int x){
	auto cur=F(x);
	if(cur.se>8) return 0;
	else return (cur.fi<<cur.se)%256;
}
int C(ll x,ll y){//mod 256
	//cout << "C " << x << ' ' << y << "=";
	if(y<0 || y>x) return 0;
	auto a=F(x);
	auto b=F(y);
	auto c=F(x-y);
	int cur=a.fi*inv[b.fi]*inv[c.fi]%256;
	int di=a.se-b.se-c.se;
	if(di>8) return 0;
	//cout << (cur<<di)%256 << endl;
	return (cur<<di)%256;
}
void solve(){
	n=0;
	ll s=0;
	for(int i=0; i<iu ;i++) f[i]={0,i};
	{
		int k;cin >> k;
		for(int i=0; i<k ;i++){
			int x,y;cin >> x >> y;f[x]={y,x};
			n+=y;
			s+=x*y;
		}
	}
	sort(f,f+iu);
	ll z255=0,z257=0;
	{//compute mod 255
		ll z3=pwf(s%3,n,3);
		ll z5=pwf(s%5,n,5);
		ll z17=pwf(s%17,n,17);
		while(true){//CRT
			if(z255%3==z3 && z255%5==z5 && z255%17==z17) break;
			z255++;
		}
	}
	{
		if(n>=2*iu && n-f[iu-1].fi>=iu);//mod 257 = 0 
		else{
			for(int i=0; i<2 ;i++){
				for(int j=0; j<=256 ;j++){
					for(int k=0; k<iu ;k++){
						w[i][j][k]=0;c[i][j][k]=0;
					}
				}
			}
			w[0][0][0]=1;c[0][0][0]=1;
			int cur=0,prv=1;
			for(int i=0; i<iu-1 ;i++){
				for(int j=0; j<f[i].fi ;j++){
					cur^=1;prv^=1;
					int x=f[i].se;
					for(int j=0; j<257 ;j++){
						for(int k=0; k<iu ;k++){
							w[cur][j][k]=0;c[cur][j][k]=0;
						}
					}
					for(int j=0; j<257 ;j++){
						for(int k=0; k<iu ;k++){
							int nj=((j+x)>=257)?j+x-257:j+x;
							if(!c[prv][j][k]) continue;
							if(k+1<iu) w[cur][nj][k+1]+=w[prv][j][k],c[cur][nj][k+1]=true;//use
							w[cur][j][k]+=w[prv][j][k],c[cur][j][k]=true;//not use
						}
					}
					
				}
			}
			bool die=false;
			z257=1;
			for(int i=0; i<257 ;i++){
				for(int j=0; j<iu ;j++){
					int x=f[iu-1].fi;
					int y=n/2-j;
					if(y>x || y<0 || !c[cur][i][j]) continue;
					//cout << "?? " << i << ' ' << j << ' ' << x << ' ' << y << endl;
					int z=(i+y*f[iu-1].se)%257;
					z=(s+2*(257-z))%257;
					if(z==0) z257=0;
					int ways=C(x,y)*w[cur][i][j]%256;
					
					//cout << s << ' ' << z << ' ' << ways << ' ' << i << ' ' << j << endl;
					z257=z257*pw(z,ways,257)%257;
					if(z257==0){
						die=true;break;
					}
					
				}
				if(die) break;
			}
			//cout << z257 << ' '<<  n << ' ';
			z257=pw(z257,F2(n/2),257);
			z257=pw(z257,F2((n+1)/2),257);
			//cout << z257 << endl;
		}
	}
	
	//cout << z255 << ' ' << z257 << endl;
	while(z255%257!=z257) z255+=255;
	cout << z255 << '\n';
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	pre();
	int t;cin >> t;
	while(t--) solve();
}