#include <bits/stdc++.h>
using namespace std;
const __int128_t INF = 1000000000000000000;
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 = INF;
    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;
    }
  }
  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;
    }
    __int128_t alpha = A[idx][idx], beta = A[idx + 1][idx + 1];
    __int128_t delta = gcd(alpha, beta);
    pair<__int128_t, __int128_t> t = ext_gcd(alpha, beta);
    __int128_t 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<__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++;
      }
    }
  }
}

answer.code: In function ‘bool solve(int, int, std::vector<std::vector<__int128> >, std::vector<__int128>)’:
answer.code:54:57: error: call of overloaded ‘abs(__gnu_cxx::__alloc_traits<std::allocator<__int128>, __int128>::value_type&)’ is ambiguous
   54 |         if (A[j][k] != 0 && (p1 == -1 && p2 == -1 || abs(A[j][k]) < mn)){
      |                                                      ~~~^~~~~~~~~
In file included from /usr/include/c++/13/cstdlib:79,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:42,
                 from answer.code:1:
/usr/include/stdlib.h:840:12: note: candidate: ‘int abs(int)’
  840 | extern int abs (int __x) __THROW __attribute__ ((__const__)) __wur;
      |            ^~~
In file included from /usr/include/c++/13/cstdlib:81:
/usr/include/c++/13/bits/std_abs.h:79:3: note: candidate: ‘constexpr long double std::abs(long double)’
   79 |   abs(long double __x)
      |   ^~~
/usr/include/c++/13/bits/std_abs.h:75:3: note: candidate: ‘constexpr float std::abs(float)’
   75 |   abs(float __x)
      |   ^~~
/usr/include/c++/13/bits/std_abs.h:71:3: note: candidate: ‘constexpr double std::abs(double)’
   71 |   abs(double __x)
      |   ^~~
/usr/include/c++/13/bits/std_abs.h:61:3: note: candidate: ‘long long int std::abs(long long int)’
   61 |   abs(long long __x) { return __builtin_llabs (__x); }
      |   ^~~
/usr/include/c++/13/bits/std_abs.h:56:3: note: candidate: ‘long int std::abs(long int)’
   56 |   abs(long __i) { return __builtin_labs(__i); }
      |   ^~~
answer.code:57:19: error: call of overloaded ‘abs(__gnu_cxx::__alloc_traits<std::allocator<__int128>, __int128>::value_type&)’ is ambiguous
   57 |           mn = abs(A[j][k]);
      |                ~~~^~~~~~~~~
/usr/include/stdlib.h:840:12: note: candidate: ‘int abs(int)’
  840 | extern int abs (int __x) __THROW __attribute__ ((__const__)) __wur;
      |            ^~~
/usr/include/c++/13/bits/std_abs.h:79:3: note: candidate: ‘constexpr long double std::abs(long double)’
   79 |   abs(long double __x)
      |   ^~~
/usr/include/c++/13/bits/std_abs.h:75:3: note: candidate: ‘constexpr float std::abs(float)’
   75 |   abs(float __x)
      |   ^~~
/usr/include/c++/13/bits/std_abs.h:71:3: note: candidate: ‘constexpr double std::abs(double)’
   71 |   abs(double __x)
      |   ^~~
/usr/include/c++/13/bits/std_abs.h:61:3: note: candidate: ‘long long int std::abs(long long int)’
   61 |   abs(long long __x) { return __builtin_llabs (__x); }
      |   ^~~
/usr/include/c++/13/bits/std_abs.h:56:3: note: candidate: ‘long int std::abs(long int)’
   56 |   abs(long __i) { return __builtin_labs(__i); }
      |   ^~~
In file included from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:58:
/usr/include/c++/13/numeric: In instantiation of ‘constexpr std::common_type_t<_Mn, _Nn> std::gcd(_Mn, _Nn) [with _Mn = __int128; _Nn = __int128; common_type_t<_Mn, _Nn> = __int128]’:
answer.code:123:27:   required from here
/usr/include/c++/13/numeric:166:21: error: static assertion failed: std::gcd arguments must be integers
  166 |       static_assert(is_integral_v<_Mn> && is_integral_v<_Nn>,
      |                     ^~~~~~~~~~~~~~~~~~
/usr/include/c++/13/numeric:166:21: note: ‘std::is_integral_v<__int128>’ evaluates to false
In file included from /usr/include/c++/13/bits/stl_pair.h:60,
                 from /usr/include/c++/13/bits/stl_algobase.h:64,
                 from /usr/include/c++/13/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51:
/usr/include/c++/13/type_traits: In instantiation of ‘struct std::make_unsigned<__int128>’:
/usr/include/c++/13/type_traits:1983:11:   required by substitution of ‘template<class _Tp> using std::make_unsigned_t = typename std::make_unsigned::type [with _Tp = __int128]’
/usr/include/c++/13/numeric:173:24:   required from ‘constexpr std::common_type_t<_Mn, _Nn> std::gcd(_Mn, _Nn) [with _Mn = __int128; _Nn = __int128; common_type_t<_Mn, _Nn> = __int128]’
answer.code:123:27:   required from here
/usr/include/c++/13/type_traits:1836:62: error: invalid use of incomplete type ‘class std::__make_unsigned_selector<__int128, false, false>’
 1836 |     { typedef typename __make_unsigned_selector<_Tp>::__type type; };
      |                                                              ^~~~
/usr/include/c++/13/type_traits:1744:11: note: declaration of ‘class std::__make_unsigned_selector<__int128, false, false>’
 1744 |     class __make_unsigned_selector;
      |           ^~~~~~~~~~~~~~~~~~~~~~~~