def check(A):
    n = len(A)
    m = len(A[0]) - 1
    s = 0

    def SwapRows(i, j):
        if i != j:
            A[i], A[j] = A[j], A[i]

    def SwapCols(i, j):
        if i != j:
            for t in range(n):
                A[t][i], A[t][j] = A[t][j], A[t][i]

    # A[:,j] += A[:,i] * c
    def AddCol(i, j, c):
        if c != 0:
            for t in range(n):
                A[t][j] += A[t][i] * c

    # A[j] += A[i] * c
    def AddRow(i, j, c):
        if c != 0:
            for t in range(m + 1):
                A[j][t] += A[i][t] * c

    def MulRow(i, c):
        for t in range(m + 1):
            A[i][t] *= c

    def MulCol(i, c):
        for t in range(n):
            A[t][i] *= c

    while s < n and s < m:
        if A[s][s] == 0:
            for i in range(s, n):
                for j in range(s, m):
                    if A[i][j] != 0:
                        SwapRows(i, s)
                        SwapCols(i, s)
                        assert A[s][s] != 0
                        break
                if A[s][s] != 0:
                    break
        if A[s][s] == 0:
            break
        while True:
            ok = True
            if A[s][s] < 0:
                MulRow(s, -1)
            assert A[s][s] > 0

            for j in range(s + 1, m):
                if A[s][j] % A[s][s] != 0:
                    value = A[s][j] // A[s][s]
                    if value * A[s][s] > A[s][j]:
                        value -= 1
                    AddCol(s, j, -value)
                    ok = False
                    SwapCols(j, s)
                    break

            if not ok:
                continue

            for j in range(s + 1, n):
                if A[j][s] % A[s][s] != 0:
                    value = A[j][s] // A[s][s]
                    if value * A[s][s] > A[j][s]:
                        value -= 1
                    AddRow(s, j, -value)
                    ok = False
                    SwapRows(j, s)
                    break

            if not ok:
                continue

            for j in range(s + 1, m):
                value = A[s][j] // A[s][s]
                if value * A[s][s] > A[s][j]:
                    value -= 1
                AddCol(s, j, -value)
                assert A[s][j] == 0

            for j in range(s + 1, n):
                value = A[j][s] // A[s][s]
                if value * A[s][s] > A[j][s]:
                    value -= 1
                AddRow(s, j, -value)
                assert A[j][s] == 0

            for i in range(s + 1, n):
                for j in range(s + 1, m):
                    if A[i][j] % A[s][s] == 0:
                        continue
                    AddRow(i, s, 1)
                    ok = False
                    break
                if not ok:
                    break

            if not ok:
                continue

            break
        if A[s][m] % A[s][s] != 0:
            return False
        s += 1
    for i in range(s, n):
        if A[i][m] != 0:
            return False
    return True


choose = [[0 for j in range(40)] for i in range(40)]
for i in range(len(choose)):
    choose[i][0] = 1
    choose[i][i] = 1
    for j in range(1, i):
        choose[i][j] = choose[i - 1][j] + choose[i - 1][j - 1]


def solve():
    n = int(input())
    x = [0] * n
    y = [0] * n
    for i in range(n):
        x[i], y[i] = map(int, input().split())

    def check2(m):
        a = [[0 for j in range(m + 2)] for i in range(n)]
        for i in range(n):
            a[i][-1] = y[i]
            for j in range(m + 1):
                a[i][j] = choose[x[i]][j]
        return check(a)

    rb = n + 1
    while not check2(rb):
        rb *= 2

    lb = -1
    while rb - lb > 1:
        mid = (lb + rb) // 2
        if check2(mid):
            rb = mid
        else:
            lb = mid

    print(rb)


t = int(input())
for _ in range(t):
    solve()

answer.code:15:7: error: invalid preprocessing directive #A
   15 |     # A[:,j] += A[:,i] * c
      |       ^
answer.code:21:7: error: invalid preprocessing directive #A
   21 |     # A[j] += A[i] * c
      |       ^
answer.code:1:1: error: ‘def’ does not name a type
    1 | def check(A):
      | ^~~