#include <bits/stdc++.h>
#define MX 256
#define PR 257
using namespace std;
typedef long long int ll;

const uint mod=65535;
struct mint{
	uint v;
	mint(ll vv=0){s(vv%mod+mod);}
	mint&s(uint vv){
		v=vv<mod?vv:vv-mod;
		return *this;
	}
	mint operator-()const{return mint()-*this;}
	mint&operator+=(const mint&r){return s(v+r.v);}
	mint&operator-=(const mint&r){return s(v+mod-r.v);}
	mint&operator*=(const mint&r){v=(unsigned ll)v*r.v%mod;return *this;}
	mint&operator/=(const mint&r){return *this*=r.inv();}
	mint operator+(const mint&r)const{return mint(*this)+=r;}
	mint operator-(const mint&r)const{return mint(*this)-=r;}
	mint operator*(const mint&r)const{return mint(*this)*=r;}
	mint operator/(const mint&r)const{return mint(*this)/=r;}
	mint pow(ll n)const{
		if(n<0)return inv().pow(-n);
		mint res(1),x(*this);
		while(n){
			if(n&1)res*=x;
			x*=x;
			n>>=1;
		}
		return res;
	}
	mint inv()const{return pow(mod-2);}
};
int cnt[MX];
bitset<PR> dp[2*PR];
void solve(){
	int k2;
	scanf("%d",&k2);
	memset(cnt,0,sizeof(cnt));
	int n=0;
	for(int i=0;i<k2;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		cnt[a]=b;
		n+=b;
	}
	if(n<=15){
		vector <int> vec;
		for(int i=0;i<MX;i++){
			for(int j=0;j<cnt[i];j++){
				vec.push_back(i);
			}
		}
		ll fac=1;
		for(int i=1;i<=n/2;i++) fac*=i;
		for(int i=1;i<=(n+1)/2;i++) fac*=i;
		mint ret=1;
		for(int S=0;S<1<<n;S++){
			int c=0;
			for(int i=0;i<n;i++) if(S>>i&1) c++;
			if(c!=n/2) continue;
			mint score=0;
			for(int i=0;i<n;i++){
				if(S>>i&1) score+=vec[i]*256;
				else score+=vec[i];
			}
			ret*=score.pow(fac);
		}
		printf("%u\n",ret.v);
	} else{
		mint sum=0;
		for(int i=0;i<MX;i++){
			sum+=(ll) i*cnt[i];
		}
		int mx=0,p=0;
		for(int i=0;i<MX;i++){
			if(mx<cnt[i]){
				mx=cnt[i];
				p=i;
			}
		}
		bool up=false;
		if(n-mx<PR*2){
			int z=min(n/2,n-mx);
			for(int i=0;i<=z;i++) dp[i].reset();
			dp[0][0]=1;
			for(int i=0;i<MX;i++){
				if(i==p) continue;
				for(int j=0;j<cnt[i];j++){
					for(int k=z;k>0;k--){
						dp[k]|=dp[k-1]<<i;
						if(i>0) dp[k]|=dp[k-1]>>(PR-i);
					}
				}
			}
			for(int i=0;i<=z;i++){
				for(int j=0;j<PR;j++){
					if(dp[i][j]&&i+mx>=n/2){
						ll cur=(j+(ll) (n/2-i)*p)%PR;
						if(cur*2==sum.v%PR){
							up=true;
						}
					}
				}
			}
		} else up=true;
		for(int ans=0;ans<mod;ans++){
			bool ok=true;
			for(int k=0;k<=3;k++){
				int c=(1<<(1<<k))+1;
				if(k!=3){
					if(sum.v%c==0){
						if(ans%c!=0) ok=false;
					} else{
						if(ans%c!=1) ok=false;
					}
				} else{
					if(up){
						if(ans%c!=0) ok=false;
					} else{
						if(ans%c!=1) ok=false;
					}
				}
			}
			if(ok){
				printf("%d\n",ans);
			}
		}
	}
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--) solve();
}