def add(n, a, x):
    for i in range(n):
        o = a[i][i]
        while x[i] != 0:
            t = a[i][i] // x[i]
            for j in range(i, n):
                a[i][j] -= x[j] * t
            a[i], x = x, a[i]
    for i in range(n):
        if a[i][i] != 0:
            for j in range(i):
                t = a[j][i] // a[i][i]
                for k in range(i, n):
                    a[j][k] -= t * a[i][k]

def check(n, a, x):
    for i in range(n):
        if x[i] != 0:
            if a[i][i] == 0 or x[i] % a[i][i] != 0:
                return False
            t = x[i] // a[i][i]
            for j in range(i, n):
                x[j] -= a[i][j] * t
    return True

def solve():
    n = int(input())
    a = [[0] * n for i in range(n)]
    x = [0] * n
    y = [0] * n
    cd = []
    for i in range(n):
        cd.append(tuple(map(int, input().split())))
    cd.sort()
    for i in range(n):
        x[i], y[i] = cd[i]
    ans = 0
    v = [1] * n
    add(n, a, list(v))
    
    while not check(n, a, list(y)):
        ans += 1
        for i in range(n):
            v[i] = v[i] * (x[i] - ans + 1) // ans
        add(n, a, list(v))
    print(ans)

T = int(input())
for case in range(T):
    solve()