牛逼题，没见过对模数这么分析性质的。
首先我们发现\(65535=65536-1=3\times 5\times 17\times 257\)，所以考虑逐个质数求出答案然后CRT合并。
可以发现\(65536\bmod 65535=1\)，所以相当于填在奇数位的对总和的贡献就是这个值，填在偶数位的对总和的贡献是这个值乘\(256\)。
对于\(3,5,17\)这三个质数，发现一个数填在每个位置的值是一样的，因此总和就是\((\sum d)^{n~!}\)
对于\(257\)，发现相当于填在奇数的数的和减去填在偶数的数的和。
对于\(n\leq 11\)的情况直接暴力枚举。
对于\(n>11\)的情况，考虑一种将每个数分在奇偶数位的方案，要乘一个\(\lfloor\frac{n}{2}\rfloor!\lceil \frac{n}{2}\rceil!\)的系数，而当\(n>11\)时这个数一定被整除\(\phi(p)=p-1\)，因此答案只能为\(0\)或\(1\)，取决于是否有一个方案的和可以被\(257\)整除。
过大的\(n\)显然无法直接dp，但是如果能把\(n\)缩小到一个和\(p\)接近的量级就是可以dp的。
考虑寻找一个充分条件。我们考虑有\(257\)个数，试着证明其一定有一个子集模\(257\)为任何书，为此可以加上强限制，限定其至少有一个区间模\(257\)为某个数，这个显然前缀和之后抽屉原理即可。
同样的，对于\(n>514\)个数，考虑选出\(\frac{n}{2}\)个数放在一遍，剩下的放在另一边，并能能够在两边选出\(257\)二元组\((x,y)\)满足\(x\not =y\)，则就能调过去。
因此我们剩下的只有\(n\leq 514\)的情况，和\(n-Mx\leq 257\)的情况，这种情况直接bitset优化dp即可，时间复杂度\(O(\frac{p^3}{w})\)。
code:
#include<bits/stdc++.h>
#define Gc() getchar()
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n))
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define PB push_back
using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned ll;
using namespace std;const int N=257+5,M=10+5,K=1e5+5,mod=1e9+7,Mod=mod-1,INF=2e9+7;const db eps=1e-5;mt19937 rnd(263082);
int n,X[N],Y[N],m,B[N*2],Bh;
ll mpow(ll x,int y,int p){ll Ans=1;while(y) y&1&&(Ans=Ans*x%p),y>>=1,x=x*x%p;return Ans;}
int GS(int p){
int Ct=0,i;for(i=1;i<=n;i++) Ct=(Ct+1ll*X[i]*Y[i])%p;if(!Ct) return 0;
ll Ans=1;for(i=1;Ans&&i<=m;i++) Ans=Ans*i%(p-1);return mpow(Ct,Ans,p);
}
bitset<N> f[N],g[N],Cl;
int CK(){
int Mx=0,i,j,h;for(i=1;i<=n;i++) Mx=max(Mx,Y[i]);if(m>=514&&m-Mx>=257) return 1;
Bh=0;for(i=1;i<=n;i++) if(Y[i]==Mx){Mx=0;}else for(j=1;j<=Y[i];j++) B[++Bh]=X[i];
for(i=0;i<=257;i++) f[i]=Cl;f[0][0]=1;
for(i=1;i<=Bh;i++){
for(j=0;j<=min(Bh,m/2);j++) g[j]=f[j],f[j]=Cl;
for(j=0;j<=min(Bh,m/2);j++){
f[j]|=g[j]<<B[i];f[j]|=g[j]>>257-B[i];
f[j+1]|=g[j]>>B[i];f[j+1]|=g[j]<<257-B[i];
//if(g[j][h]) f[j][(h+B[i])%257]=1,f[j+1][(h-B[i]+257)%257]=1;
}
}
for(i=1;i<=n;i++)Mx=max(Mx,Y[i]);for(i=1;i<=n;i++) if(Y[i]==Mx){
for(j=max(0,m/2-Bh);j<=min(m/2,Y[i]);j++) if(f[m/2-j][(1ll*(2*j-Y[i])*X[i]%257+257)%257]) return 1;
return 0;
}
}
int GA(){
if(CK()) return 0;if(m>=12) return 1;
int i,j;Bh=0;for(i=1;i<=n;i++) for(j=1;j<=Y[i];j++) B[++Bh]=X[i];
ll As=1;for(i=0;i<(1<<m);i++){
int Ct=0;for(j=0;j<m;j++) Ct+=(i>>j&1);if(Ct^(m/2)) continue;
int Ts=0;for(j=1;j<=m;j++) Ts+=(i>>(j-1)&1?-B[j]:B[j]);As=As*(Ts%257+257)%257;
}
ll Fc=1;for(i=1;i<=m/2;i++) Fc=Fc*i%256;for(i=1;i<=(m+1)/2;i++) Fc=Fc*i%256;return mpow(As,Fc,257);
}
void Solve(){
int i,j;scanf("%d",&n);m=0;for(i=1;i<=n;i++) scanf("%d%d",&X[i],&Y[i]),m+=Y[i];
int A1=GS(3),A2=GS(5),A3=GS(17),A4=GA();
for(i=0;i<65535;i++) if(i%3==A1&&i%5==A2&&i%17==A3&&i%257==A4) {printf("%d\n",i);return;}
}
int main(){
freopen("1.in","r",stdin);
int t;scanf("%d",&t);while(t--) Solve();
}