#include<iostream>
#include<cstdio>
#include<bitset>
#define N 514
#define mod 65535
#define mod2 32768
using namespace std;
const int inf=(int)(1e9);
const int inv2=(mod+1)>>1;
const int delta[4]={3,5,17,257};
int read()
{
	char c=0;
	int sum=0;
	while (c<'0'||c>'9') c=getchar();
	while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
	return sum;
}
int MD(int x)
{
	return x>=mod?x-mod:x;
}
int MD2(int x)
{
	return x<0?x+mod:x;
}
void Adder(int &x,int d)
{
	x+=d;
	if (x>=mod) x-=mod;
	return;
}
void Adder2(int &x,int d)
{
	x+=d;
	if (x<0) x+=mod;
	return;
}
int T,k,ans,ans2,a,b,n,cnt[N+1],scnt[N+1],tong[N+1];
bitset<N+1>used[N+1];
bitset<N+1>used2[N+1];
int fast_pow(int a,int b)
{
	int res=1,mul=a;
	while (b)
	{
		if (b&1) res=1ll*res*mul%mod;
		mul=1ll*mul*mul%mod,b>>=1;
	}
	return res;
}
int main()
{
	int maxn,rt,rcnt,res,ps;
	long long rst;
	bool op;
	T=read();
	while (T--)
	{
		k=read(),n=ans=0,ans2=1;
		for (int i=0;i<=255;++i) cnt[i]=0;
		for (int i=1;i<=k;++i) cnt[read()]=read();
		for (int i=0;i<=255;++i) n+=cnt[i],Adder(ans,1ll*i*cnt[i]%mod);
		if (n<=18)
		{
			ps=0,ans=1;
			for (int i=0;i<=255;++i)
				for (int j=1;j<=cnt[i];++j)
					tong[++ps]=i;
			for (int i=0;i<(1<<n);++i)
				if (__builtin_popcount(i)==((n+1)>>1))
				{
					res=0;
					for (int j=1;j<=n;++j)
					{
						if (!((i>>(j-1))&1)) res=MD(res+256*tong[j]%mod);
						else Adder(res,tong[j]);
					}
					ans=1ll*ans*res%mod;
				}
			rst=1;
			for (int i=1;i<=(n>>1);++i) rst*=i;
			for (int i=1;i<=((n+1)>>1);++i) rst*=i;
			if (rst>=mod2) rst=rst%mod2+mod2;
			ans=fast_pow(ans,rst),printf("%d\n",ans);
		}
		else
		{
			ans=fast_pow(ans,mod2);
			for (int i=0;i<=3;++i)
			{
				maxn=-inf,rt=res=op=rcnt=0;
				for (int j=0;j<delta[i];++j) scnt[j]=0;
				for (int j=0;j<=255;++j) scnt[j%delta[i]]+=cnt[j];
				for (int j=0;j<delta[i];++j) res=(res+1ll*j*scnt[j])%delta[i];
				res=1ll*res*((delta[i]+1)>>1)%delta[i];
				for (int j=0;j<delta[i];++j)
					if (scnt[j]>maxn)
						maxn=scnt[j],rt=j;
				for (int j=0;j<delta[i];++j)
					if (rt!=j)
						rcnt+=scnt[j];
				if (min(rcnt,n>>1)>=delta[i]) op=1;
				else
				{
					for (int j=0;j<delta[i];++j) used[j].reset();
					used[0][0]=1;
					for (int j=0;j<delta[i];++j)
						if (rt!=j)
						{
							for (int k=1;k<=scnt[j];++k)
							{
								for (int t=0;t<delta[i];++t) used2[(t+j)%delta[i]]=used[t]<<1;
								for (int t=0;t<delta[i];++t) used[t]|=used2[t];
							}
						}
					for (int j=0;j<delta[i];++j)
						for (int k=0;k<=min(((n+1)>>1),rcnt);++k)
							if (used[j][k]&&(1ll*(((n+1)>>1)-k)*rt+j)%delta[i]==res)
								op=1;
				}
				if (op) ans2=1ll*ans2*fast_pow(delta[i],mod2)%mod;
			}
			a=1ll*MD(ans+ans2)*inv2%mod,b=1ll*MD2(ans-ans2)*inv2%mod,printf("%d\n",MD(a+256ll*b%mod));
		}
	}
	return 0;
}