T=int(input())
def gcd(n,m):
	if m==0:
		return n
	else:
		return gcd(m,n%m)
def binom(n,m):
	if 0>m or m>n:
		return 0
	else:
		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(' '))
	def chk(x,y,k):
		# print("chk",x,y,k)
		a=[[0 for i in range(k+2)] for j in range(n)]
		for i in range(n):
			a[i][k+1]=y[i]
			for j in range(k+1):
				a[i][j]=binom(x[i],j)
		for i in range(min(n,k+1)):
			for j in range(i+1,n):
				while a[j][i]:
					w=a[i][i]//a[j][i]
					for p in range(k+2):
						a[i][p]-=a[j][p]*w
					a[j],a[i]=a[i],a[j]
		for i in range(n):
			g=0
			for j in range(k+1):
				g=gcd(g,a[i][j])
			if g==0:
				if a[i][k+1]!=0:
					return 0
			else:
				if a[i][k+1]%g!=0:
					return 0
		# print(a)
		return 1
	ans=0
	while not chk(x,y,ans):
		ans+=1
	print(ans)
	T-=1