#include <bits/stdc++.h>
using namespace std;
const long long INF = 1000000000000000000;
pair<long long, long long> ext_gcd(long long a, long long b){
  if (a > b){
    pair<long long, long long> S = ext_gcd(b, a);
    return make_pair(S.second, S.first);
  }
  if (b % a == 0){
    return make_pair(1, 0);
  } else {
    pair<long long, long long> 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<long long>> A, vector<long long> 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, long long 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, long long 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;
    long long mn = INF;
    for (int j = i; j < N; j++){
      for (int k = i; k < M; k++){
        if (A[j][k] != 0 && 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;
    }
  }
  while (true){
    int idx = -1;
    for (int i = 0; i < r - 1; i++){
      if (A[i + 1][i + 1] % A[i][i] != 0){
        idx = i;
        break;
      }
    }
    if (idx == -1){
      break;
    }
    long long alpha = A[idx][idx], beta = A[idx + 1][idx + 1];
    long long delta = gcd(alpha, beta);
    pair<long long, long long> t = ext_gcd(alpha, beta);
    long long theta = t.first, rho = t.second;
    row_add(idx + 1, rho, idx);
    col_swap(idx, idx + 1);
    col_add(idx + 1, theta, idx);
    row_invert(idx + 1);
    row_add(idx, beta / delta, idx + 1);
    col_add(idx, -alpha / delta, idx + 1);
  }
  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<long long>> binom(31, vector<long long>(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<long long> x(n), y(n);
    for (int j = 0; j < n; j++){
      cin >> x[j] >> y[j];
    }
    if (y == vector<long long>(0)){
      cout << 0 << endl;
    } else {
      int K = 1;
      while (true){
        vector<vector<long long>> A(n, vector<long long>(K, 0));
        for (int j = 0; j < n; j++){
          for (int k = 0; k < K; k++){
            A[j][k] = binom[x[j]][k];
          }
        }
        vector<long long> B = y;
        if (solve(n, K, A, B)){
          cout << K - 1 << endl;
          break;
        }
        K++;
      }
    }
  }
}