#include<bits/stdc++.h>
using namespace std;
const int N=40;
typedef __int128 ll;
int T,n=N-2,x[N],y[N];ll C[N][N],A[N][N];
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
void printA(int n,int m){
    cout<<"A:\n";
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++)
            cout<<(int)A[i][j]<<' ';
        cout<<"\n";
    }
}
ll exgcd(ll a,ll b,ll&x,ll&y){
    if(b==0){x=1;y=0;return a;}
    ll d=exgcd(b,a%b,y,x);y=(d-a*x)/b;
    return d;
}
void smith(ll A[N][N],int n,int m){
    auto print=[&](){
        for(int i=0;i<n;i++){
            for(int j=0;j<=m;j++)
                cout<<(long long)A[i][j]<<' ';
            cout<<"\n";
        }
    };
    auto opt=[&](int i){
        for(int y=i+1;y<m;y++)if(A[i][y]){
            ll s,t;ll d=exgcd(A[i][i],A[i][y],s,t);
            ll u=-A[i][y]/d,v=A[i][i]/d;
            for(int j=i;j<n;j++){
                ll tmp1=A[j][i],tmp2=A[j][y];
                A[j][i]=s*tmp1+t*tmp2;A[j][y]=u*tmp1+v*tmp2;
            }
            assert(A[i][y]==0);
        }
        for(int x=i+1;x<n;x++)if(A[x][i]){
            ll s,t;ll d=exgcd(A[i][i],A[x][i],s,t);
            ll u=-A[x][i]/d,v=A[i][i]/d;
            for(int j=i;j<=m;j++){
                ll tmp1=A[i][j],tmp2=A[x][j];
                A[i][j]=s*tmp1+t*tmp2;A[x][j]=u*tmp1+v*tmp2;
            }
            assert(A[x][i]==0);
        }
    };
    for(int i=0;i<min(n,m);i++){
        int px=-1,py=-1;
        for(int x=i;x<n;x++)
            for(int y=i;y<m;y++)if(A[x][y])px=x,py=y;
        if(px==-1)break;
        for(int x=i;x<n;x++)swap(A[x][i],A[x][py]);
        for(int y=i;y<=m;y++)swap(A[i][y],A[px][y]);
        opt(i);if(i>=1&&A[i][i]%A[i-1][i-1]!=0){
            for(int j=i;j<n;j++)A[i-1][j]+=A[i][j];
            opt(i-1);//assert(A[i][i]%A[i-1][i-1]==0);
        }
    }
}
bool check(int deg){
    for(int i=0;i<n;i++){
        for(int j=0;j<=deg;j++)
            A[i][j]=C[x[i]][j];
        A[i][deg+1]=y[i];
    }
    int m=deg+1;smith(A,n,m);//printA(n,m+1);cout<<"\n";
    int rA=0;for(;rA<min(n,m)&&A[rA][rA];rA++);if(A[rA][deg+1])return false;
    for(int i=0;i<rA;i++)if(A[i][deg+1]%A[i][i]!=0)return false;
    return true;
}
void solve(){
    cin>>n;
    for(int i=0;i<n;i++)cin>>x[i]>>y[i];
    for(int i=0;i<N-4;i++)
        if(check(i)){cout<<i<<"\n";break;}
}
int main(){
    ios::sync_with_stdio(false);
    for(int i=0;i<=n;i++)
        for(int j=0;j<=i;j++)
            C[i][j]=(j?C[i-1][j-1]+C[i-1][j]:1);
    cin>>T;while(T--)solve();
    return 0;
}