#!/usr/bin/python3

def has_int_solution(A, b):
    N = len(A)
    if N == 0:
        return True

    M = len(A[0])
    col = 0
    for row in range(N):
        non_zero = col
        while non_zero < M and A[row][non_zero] == 0:
            non_zero += 1
        
        if non_zero == M:
            if b[i] != 0:
                return False
            continue
        
        if non_zero != col:
            for i in range(row, N):
                A[i][col], A[i][non_zero] = A[i][non_zero], A[i][col]

        for j in range(col, M):
            if A[row][j] < 0:
                for i in range(row, N):
                    A[i][j] *= -1

        assert A[row][col] > 0

        for j in range(col + 1, M):
            while A[row][j] != 0:
                K = A[row][col] // A[row][j]
                for i in range(row, N):
                    A[i][col] -= A[i][j] * K
                    A[i][col], A[i][j] = A[i][j], A[i][col]

        if b[row] % A[row][col] != 0:
            return False

        K = b[row] // A[row][col]
        for i in range(row + 1, N):
            b[i] -= A[i][col] * K

        col += 1
    
    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())
    points = []
    for i in range(n):
        points.append(tuple(map(int, input().split())))
    
    points.sort()

    def check(deg):
        A = [[choose[points[i][0]][j] for j in range(deg + 1)] for i in range(n)]
        b = [points[i][1] for i in range(n)]
        return has_int_solution(A, b)

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

    print(rb)

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