#include <bits/stdc++.h>
using namespace std;
__int128_t abs(__int128_t a){
  return max(a, -a);
}
__int128_t gcd(__int128_t a, __int128_t b){
  while (b > 0){
    a %= b;
    swap(a, b);
  }
  return a;
}
pair<__int128_t, __int128_t> ext_gcd(__int128_t a, __int128_t b){
  if (a > b){
    pair<__int128_t, __int128_t> S = ext_gcd(b, a);
    return make_pair(S.second, S.first);
  }
  if (b % a == 0){
    return make_pair(1, 0);
  } else {
    pair<__int128_t, __int128_t> S = ext_gcd(b % a, a);
    return make_pair(S.second - b / a * S.first, S.first);
  }
}
bool solve(int N, int M, vector<vector<__int128_t>> A, vector<__int128_t> B){
  auto row_swap = [&](int i1, int i2){
    swap(A[i1], A[i2]);
    swap(B[i1], B[i2]);
  };
  auto col_swap = [&](int j1, int j2){
    for (int i = 0; i < N; i++){
      swap(A[i][j1], A[i][j2]);
    }
  };
  auto row_invert = [&](int i){
    for (int j = 0; j < M; j++){
      A[i][j] *= -1;
    }
    B[i] *= -1;
  };
  auto col_invert = [&](int j){
    for (int i = 0; i < N; i++){
      A[i][j] *= -1;
    }
  };
  auto row_add = [&](int i1, __int128_t c, int i2){
    for (int j = 0; j < M; j++){
      A[i2][j] += A[i1][j] * c;
    }
    B[i2] += B[i1] * c;
  };
  auto col_add = [&](int j1, __int128_t c, int j2){
    for (int i = 0; i < N; i++){
      A[i][j2] += A[i][j1] * c;
    }
  };
  int r = 0;
  for (int i = 0; i < min(N, M); i++){
    int p1 = -1, p2 = -1;
    __int128_t mn = -1;
    for (int j = i; j < N; j++){
      for (int k = i; k < M; k++){
        if (A[j][k] != 0 && (p1 == -1 && p2 == -1 || abs(A[j][k]) < mn)){
          p1 = j;
          p2 = k;
          mn = abs(A[j][k]);
        }
      }
    }
    if (p1 == -1 && p2 == -1){
      break;
    }
    r++;
    row_swap(p1, i);
    col_swap(p2, i);
    if (A[i][i] < 0){
      row_invert(i);
    }
    while (true){
      bool ok = true;
      for (int j = i + 1; j < M; j++){
        if (A[i][j] != 0){
          if (A[i][j] < 0){
            col_invert(j);
          }
          if (A[i][j] >= A[i][i]){
            col_add(i, -(A[i][j] / A[i][i]), j);
          }
          if (A[i][j] > 0){
            col_swap(i, j);
            ok = false;
            break;
          }
        }
      }
      if (!ok){
        continue;
      }
      for (int j = i + 1; j < N; j++){
        if (A[j][i] != 0){
          if (A[j][i] < 0){
            row_invert(j);
          }
          if (A[j][i] >= A[i][i]){
            row_add(i, -(A[j][i] / A[i][i]), j);
          }
          if (A[j][i] > 0){
            row_swap(i, j);
            ok = false;
            break;
          }
        }
      }
      if (!ok){
        continue;
      }
      break;
    }
  }
  bool ok = true;
  for (int i = 0; i < r; i++){
    if (B[i] % A[i][i] != 0){
      ok = false;
    }
  }
  for (int i = r; i < N; i++){
    if (B[i] != 0){
      ok = false;
    }
  }
  return ok;
}
int main(){
  vector<vector<__int128_t>> binom(31, vector<__int128_t>(31, 0));
  for (int i = 0; i < 31; i++){
    binom[i][0] = 1;
    for (int j = 1; j < i; j++){
      binom[i][j] = binom[i - 1][j - 1] + binom[i - 1][j];
    }
    binom[i][i] = 1;
  }
  int T;
  cin >> T;
  for (int i = 0; i < T; i++){
    int n;
    cin >> n;
    vector<int> x(n), y(n);
    for (int j = 0; j < n; j++){
      cin >> x[j] >> y[j];
    }
    if (y == vector<int>(0)){
      cout << 0 << endl;
    } else {
      int K = 1;
      while (true){
        vector<vector<__int128_t>> A(n, vector<__int128_t>(K, 0));
        for (int j = 0; j < n; j++){
          for (int k = 0; k < K; k++){
            A[j][k] = binom[x[j]][k];
          }
        }
        vector<__int128_t> B(n);
        for (int j = 0; j < n; j++){
          B[j] = y[j];
        }
        if (solve(n, K, A, B)){
          cout << K - 1 << endl;
          break;
        }
        K++;
      }
    }
  }
}