#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=265,M=555;
ll phi=128,mod1=255,mod2=257,phi2=256,mod3=65535;
ll buk[N];
bitset<M>f[N],g[N];
ll ans1,ans2;
ll dp[2][N][N];
ll ksm(ll a,int b,int mod){
  ll res=1;
  while(b){
    if(b&1)res=res*a%mod;
    a=a*a%mod,b>>=1;
  }
  return res;
}
ll calc255(){
  ll sum=0,cnt=0,mt=1;
  for(int i=0;i<256;i++)cnt+=buk[i],sum=(sum+buk[i]*i)%mod1;
  if(cnt>=phi)return (__gcd(sum,mod1)==1?1:ksm(sum,phi,mod1));
  if(cnt<=6){
    for(int i=1;i<=cnt;i++)mt=mt*i;
    return ksm(sum,mt,mod1);
  }
  for(int i=1;i<=cnt;i++)mt=mt*i%phi;
  return ksm(sum,mt+(__gcd(sum,mod1)==1?0:phi),mod1);
}
void upd(int x){
  for(int i=0;i<mod2;i++)
    g[(i+x)%mod2]=f[i]<<1;
  for(int i=0;i<mod2;i++)
    f[i]|=g[i];
}
ll calc257(){
  ll cnt=0,mx=0,sum=0;
  for(int i=0;i<256;i++)cnt+=buk[i],mx=(buk[i]>buk[mx]?i:mx),sum=(sum+buk[i]*i)%mod2;
  if(cnt<=12){
    memset(dp,0,sizeof(dp));
    int o=0;
    dp[o][0][0]=1;
    for(int i=0;i<256;i++)
      for(int j=1;j<=buk[i];j++){
        o^=1;
        memset(dp[o],0,sizeof(dp[o]));
        for(int k=0;k<=cnt/2;k++)
          for(int l=0;l<mod2;l++){
            dp[o][k+1][(l-i+mod2)%mod2]=(dp[o][k+1][(l-i+mod2)%mod2]+dp[o^1][k][l])%phi2;
            dp[o][k][(l+i)%mod2]=(dp[o][k][(l+i)%mod2]+dp[o^1][k][l])%phi2;
          }
      }
    if(dp[o][cnt/2][0])return 0;
    ll res=1,rt=1;
    for(int i=1;i<=cnt/2;i++)res=res*i%phi2;
    for(int i=1;i<=cnt-cnt/2;i++)res=res*i%phi2;
    for(int i=0;i<mod2;i++)
      rt=rt*ksm(i,res*dp[o][cnt/2][i]%phi2,mod2)%mod2;
    return rt;
  }
  if(cnt>=512&&cnt-buk[mx]>=256)return 0;
  f[0][0]=1;
  for(int i=0;i<256;i++){
    if(i==mx)continue;
    for(int j=1;j<=buk[i];j++)
      upd(i);
  }
  for(int i=0;i<mod2;i++)
    for(int j=0;j<=cnt/2;j++){
      if(!f[i][j])continue;
      ll lf=cnt/2-j;
      if(lf>buk[mx])continue;
      if((i+lf*mx)*2%mod2==sum)return 0;
    }
  return 1;
}
int n;
ll sum;
int TE;
void work(){
  memset(buk,0,sizeof(buk));
  for(int i=0;i<mod2;i++)f[i]=0;
  cin>>n;
  for(int i=1,x,y;i<=n;i++)cin>>x>>y,buk[x]=y;
  ans1=calc255(),ans2=calc257(),sum=0;
  sum+=ans1*ksm(2,phi-1,mod1)*mod2;
  sum+=ans2*ksm(255,phi2-1,mod2)*mod1;
  sum%=mod3;
  cout<<sum<<'\n';
}
signed main(){
  ios::sync_with_stdio(0);
  cin.tie(0),cout.tie(0);
  cin>>TE;
  while(TE--)work();
  return 0;
}