T=int(input())
def binom(n,m):
	if 0>n or m>n:
		return 0
	ans=1
	for i in range(m):
		ans=ans*(n-i)//(i+1)
	return ans
while T>0:
	n=int(input())
	x=[0 for i in range(n)]
	y=[0 for i in range(n)]
	for i in range(n):
		x[i],y[i]=map(int,input().split(' '))
	a=[[0 for j in range(n)] for i in range(n)]
	def insert(a,n,x):
		for i in range(n):
			while x[i]:
				w=a[i][i]//x[i]
				for j in range(i,n):
					a[i][j]-=x[j]*w
				a[i],x=x,a[i]
		for i in range(n):
			if a[i][i]==0:
				continue
			for j in range(i):
				w=a[j][i]/a[i][i]
				for k in range(i,n):
					a[j][k]-=a[i][k]*w
	def check(a,n,x):
		for i in range(n):
			if x[i]==0:
				continue
			if a[i][i]==0 or x[i]%a[i][i]!=0:
				return 0
			w=x[i]//a[i][i]
			for j in range(i,n):
				x[j]-=a[i][j]*w
		return 1
	ans=0
	while 1:
		v=[]
		for i in range(n):
			v.append(binom(x[i],ans))
		insert(a,n,v)
		if check(a,n,y):
			print(ans)
			break
		ans+=1
	T-=1