Read problems statements [Mandarin] , [Bengali] , [Hindi] , [Russian] and [Vietnamese] as well.

Consider a seven-segment display, which can be used to show a decimal digit ($0$ through $9$). When a digit is shown on a working display, specific segments of the display turn on, as depicted in the following image (for digits $1$ through $9$):

$0$ is depicted as usual, with all the segments turned on, except the middle one.

Some of the segments of this display (possibly all or none) are dead ― they never turn on. In order to find out which segments could be dead, we ran $N$ tests with the display. For each $i$ ($1 ≤ i ≤ N$), in the $i$-th test, we tried to show the digit $x_{i}$ and out of the $7$ segments of the display, $y_{i}$ segments turned on.

It is possible that the results of tests have been recorded incorrectly. Determine if the recorded results are valid, i.e. if there is a set of dead segments such that in each test, the recorded number of segments that turned on is correct. If it is valid, calculate the minimum possible number of dead segments and the maximum possible number of dead segments consistent with the results of the tests.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single integer $N$.
$N$ lines follow. For each $i$ ($1 ≤ i ≤ N$), the $i$-th of these lines contains two space-separated integers $x_{i}$ and $y_{i}$.

------  Output ------
For each test case:
If the results of tests are invalid, print a single line containing the string "invalid" (without quotes).
Otherwise, print a single line containing two space-separated integers ― the minimum and maximum number of dead segments.

------  Constraints ------
$1 ≤ T ≤ 1,000$
$1 ≤ N ≤ 10$
$0 ≤ x_{i} ≤ 9$ for each valid $i$
$0 ≤ y_{i} ≤ 7$ for each valid $i$
$x_{1}, x_{2}, \ldots, x_{N}$ are pairwise distinct

------  Subtasks ------
Subtask #1 (20 points): $N = 1$

Subtask #2 (80 points): original constraints

----- Sample Input 1 ------ 
2
2
2 4
5 4
2
8 6
0 7
----- Sample Output 1 ------ 
1 2
invalid

Difficulty: HARD
Tags: Mathematics

Bit manipulation

Implementation
Skill types: Bit manipulation

Starter code:

Solutions:
def solve(i):
	for k in range(n):
		(a, b) = (arr[k][0], arr[k][1])
		count = 0
		for j in range(7):
			if mask[a] & 1 << j and i & 1 << j:
				count += 1
		if count != b:
			return False
	return True
mask = [119, 36, 93, 109, 46, 107, 123, 37, 127, 111]
tests = int(input())
for te in range(tests):
	n = int(input())
	arr = []
	for i in range(n):
		arr.append(list(map(int, input().split())))
	flag = 0
	mina = 10
	maxa = -1
	for i in range(1 << 7):
		if solve(i):
			flag = 1
			count = 0
			for j in range(7):
				if i & 1 << j == 0:
					count += 1
			mina = min(mina, count)
			maxa = max(maxa, count)
	if flag == 0:
		print('invalid')
	else:
		print(mina, maxa)


num_dic = {0: '1110111', 1: '0010010', 2: '1011101', 3: '1011011', 4: '0111010', 5: '1101011', 6: '1101111', 7: '1010010', 8: '1111111', 9: '1111011'}
for z in range(int(input())):
	n = int(input())
	tuples = [tuple(map(int, input().split())) for i in range(n)]
	valid_config = []
	for i in range(128):
		valid = True
		for j in range(n):
			(x, y) = tuples[j]
			x_bin = int(num_dic[x], 2)
			tot = bin(x_bin & i)[2:].count('1')
			if tot != y:
				valid = False
		if valid:
			valid_config.append(i)
	mn = 7
	mx = 0
	for k in valid_config:
		cnt_bin = bin(k)
		cnt_bin = '0' * (7 - len(cnt_bin[2:])) + cnt_bin[2:]
		cnt = cnt_bin.count('0')
		if cnt > mx:
			mx = cnt
		if cnt < mn:
			mn = cnt
	if len(valid_config) == 0:
		print('invalid')
	else:
		print(mn, mx)


def invalid(n, l, list1, list5, max_dead):
	list2 = []
	for i in range(n):
		if len(list1[l[i][0]]) < l[i][1]:
			print('invalid')
			return
	for i in range(127):
		list3 = list5[i].copy()
		list4 = list({0, 1, 2, 3, 4, 5, 6} - set(list3))
		list4.sort()
		flag = 0
		dead = -1
		for k in range(n):
			dead = len(list1[l[k][0]]) - l[k][1]
			if dead < 0:
				print('invalid')
				return
			for m in list1[l[k][0]]:
				if dead == 0:
					if m not in list4:
						flag = 1
						break
				elif m in list3:
					dead -= 1
			if flag == 1:
				break
			if dead != 0:
				break
		if dead == 0 and flag == 0:
			list2.append(list3)
	if max_dead == 0:
		if len(list2) == 0:
			print(0, 0, sep=' ')
		else:
			print(0, len(list2[len(list2) - 1]), sep=' ')
	elif len(list2) == 0:
		print('invalid')
	else:
		print(len(list2[0]), len(list2[len(list2) - 1]), sep=' ')
t = int(input())
list1 = [[0, 1, 3, 4, 5, 6], [1, 3], [0, 1, 2, 4, 5], [0, 1, 2, 3, 4], [1, 2, 3, 6], [0, 2, 3, 4, 6], [0, 2, 3, 4, 5, 6], [0, 1, 3], [0, 1, 2, 3, 4, 5, 6], [0, 1, 2, 3, 4, 6]]
list5 = [[0], [1], [2], [3], [4], [5], [6]]
for i in range(127):
	list6 = list5[i].copy()
	for j in range(list6[len(list6) - 1] + 1, 7):
		list5.append(list6 + [j])
for i in range(t):
	n = int(input())
	l = []
	max_dead = -999
	for j in range(n):
		l1 = []
		s = input().split(' ')
		l1.append(int(s[0]))
		l1.append(int(s[1]))
		if len(list1[l1[0]]) - l1[1] > max_dead:
			max_dead = len(list1[l1[0]]) - l1[1]
		l.append(l1)
	if max_dead < 0:
		print('invalid')
		continue
	invalid(n, l, list1, list5, max_dead)


def count_alive(num):
	return bin(num).count('1')
for _ in range(int(input())):
	li = []
	for i in range(int(input())):
		(xx, yy) = map(int, input().split())
		li.append((xx, yy))
	ideal = [119, 18, 93, 91, 58, 107, 111, 82, 127, 123]
	comb = list(range(128))
	valid = 1
	for (x, y) in li:
		if y > count_alive(ideal[x]):
			valid = 0
			break
	ncomb = []
	if valid:
		for (x, y) in li:
			for j in comb:
				if count_alive(ideal[x] & j) == y:
					ncomb.append(j)
			comb = ncomb
			ncomb = []
	if len(comb) == 0:
		valid = 0
	if valid:
		alive = []
		for i in range(len(comb)):
			alive.append(count_alive(comb[i]))
		print(7 - max(alive), 7 - min(alive))
	else:
		print('invalid')


mask = [119, 36, 93, 109, 46, 107, 123, 37, 127, 111]

def NumOn(x):
	i = 1
	ans = 0
	while i < 128:
		if x & i > 0:
			ans += 1
		i = i << 1
	return ans

def NumOff(x):
	return 7 - NumOn(x)
t = int(input())
while t:
	t -= 1
	n = int(input())
	inp = [list(map(int, input().split())) for _ in range(n)]
	configs = []
	for config in range(128):
		valid = True
		for i in range(n):
			if NumOn(mask[inp[i][0]] & config) != inp[i][1]:
				valid = False
				break
		if valid:
			configs.append(config)
	if len(configs) == 0:
		print('invalid')
	else:
		max = -1
		min = 8
		for c in configs:
			dead = NumOff(c)
			if dead > max:
				max = dead
			if dead < min:
				min = dead
		print(min, max)


dicti = {1: '0110000', 2: '1101101', 3: '1111001', 4: '0110011', 5: '1011011', 6: '1011111', 7: '1110000', 8: '1111111', 9: '1111011', 0: '1111110'}
Arr = []
for i in range(2 ** 7):
	to_Append = str(bin(i))[2:]
	Arr.append('0' * (7 - len(to_Append)) + to_Append)

def check(Ans_Arr, p):
	temp_Arr = []
	no_of_ones = p[1]
	ones_places = [i for i in range(7) if dicti[p[0]][i] == '1']
	for i in Ans_Arr:
		if i.count('1') >= p[1]:
			cco = 0
			for j in ones_places:
				if i[j] == '1':
					cco += 1
			if cco == p[1]:
				temp_Arr.append(i)
	return temp_Arr
for i in range(int(input())):
	flag = False
	Ans_Arr = Arr[:]
	queries = []
	n = int(input())
	for j in range(n):
		queries.append(list(map(int, input().split())))
	for p in queries:
		if p[1] > dicti[p[0]].count('1'):
			print('invalid')
			flag = True
			break
		Ans_Arr = check(Ans_Arr, p)
		if len(Ans_Arr) == 0:
			print('invalid')
			flag = True
			break
	if not flag:
		for m in range(len(Ans_Arr)):
			Ans_Arr[m] = Ans_Arr[m].count('0')
		print(min(Ans_Arr), max(Ans_Arr))


def n1(n):
	s = bin(n)
	if s[2] == '0':
		return 0
	else:
		return s.count('1')
conf = [119, 18, 93, 91, 58, 107, 111, 82, 127, 123]
for z in range(int(input())):
	n = int(input())
	bf = []
	for i in range(128):
		bf.append(i)
	li = []
	for i in range(n):
		li.append(tuple(map(int, input().split())))
	for (x, y) in li:
		bf1 = []
		for j in bf:
			if n1(conf[x] & j) == y:
				bf1.append(j)
		if not bf1:
			print('invalid')
			break
		else:
			bf = list(set(bf) & set(bf1))
		if not bf:
			print('invalid')
			break
	else:
		mx = n1(bf[0])
		mn = mx
		for j in bf:
			mx = max(mx, n1(j))
			mn = min(mn, n1(j))
		print(7 - mx, 7 - mn)


seg = [[True, True, True, True, True, True, False], [False, False, False, True, True, False, False], [False, True, True, False, True, True, True], [False, False, True, True, True, True, True], [True, False, False, True, True, False, True], [True, False, True, True, False, True, True], [True, True, True, True, False, True, True], [False, False, False, True, True, True, False], [True] * 7, [True, False, True, True, True, True, True]]
T = int(input())
for _ in range(T):
	n = int(input())
	l = [[int(e) for e in input().split()] for _ in range(n)]
	maxOn = -1
	minOn = 8
	for segOn in range(2 ** 7):
		band = True
		bits = [1 << 6 - i & segOn >= 1 for i in range(7)]
		for (j, e) in enumerate(l):
			eq = (bits[i] and seg[e[0]][i] for i in range(7))
			if sum(eq) != e[1]:
				band = False
				break
		if band:
			a = sum(bits)
			minOn = min(minOn, 7 - a)
			maxOn = max(maxOn, 7 - a)
	if minOn == 8 and maxOn == -1:
		print('invalid')
	else:
		print('{} {}'.format(minOn, maxOn))


t = int(input())
d = {0: (1, 2, 3, 5, 6, 7), 1: (3, 7), 2: (2, 3, 4, 5, 6), 3: (2, 3, 4, 6, 7), 4: (1, 3, 4, 7), 5: (1, 2, 4, 6, 7), 6: (1, 2, 4, 5, 6, 7), 7: (2, 3, 7), 8: (1, 2, 3, 4, 5, 6, 7), 9: (1, 2, 3, 4, 6, 7)}
ll = []
for i in range(128):
	ll.append(bin(i)[2:])
for i in range(len(ll)):
	if len(ll[i]) != 7:
		di = 7 - len(ll[i])
		ll[i] = '0' * di + ll[i]
while t:
	re = []
	l = []
	n = int(input())
	for i in range(n):
		(x, y) = map(int, input().split())
		l.append((x, y))
	for j in ll:
		lol = 0
		for i in l:
			(x, y) = i
			a = d[x]
			cou = 0
			for k in a:
				if j[7 - k] == '1':
					cou += 1
			if cou != y:
				lol = 1
				break
		if lol == 0:
			re.append(j)
	mi = 10000000000000000000000
	mx = -1
	if len(re) == 0:
		print('invalid')
	else:
		for i in re:
			xc = i.count('0')
			if xc > mx:
				mx = xc
			if xc < mi:
				mi = xc
		print(mi, mx)
	t -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	f = {0: [0, {1, 2, 3, 5, 6, 7}], 1: [2, {3, 7}], 2: [5, {2, 3, 4, 5, 6}], 3: [5, {2, 3, 4, 7, 6}], 4: [4, {1, 4, 3, 7}], 5: [5, {2, 1, 4, 7, 6}], 6: [6, {1, 2, 4, 5, 6, 7}], 7: [3, {2, 3, 7}], 8: [7, {1, 2, 3, 4, 5, 6, 7}], 9: [6, {1, 2, 3, 4, 6, 7}]}
	f2 = {0: '1110111', 1: '0010001', 2: '0111110', 3: '0111011', 4: '1011001', 5: '1101011', 6: '1101111', 7: '0110001', 8: '1111111', 9: '1111011'}
	data = []
	for i in range(n):
		(no, disp) = map(int, input().split())
		data.append([no, disp])
	(min_b, max_b) = (100, -1)
	setbulb = []
	ans = []
	for i in range(128):
		poss = 1
		for j in data:
			(no, disp) = j
			x = i & int(f2[no], 2)
			y = bin(x).count('1')
			if y != disp:
				poss = 0
				break
		if poss:
			setbulb.append(i)
	if len(setbulb):
		for i in setbulb:
			y = bin(i).count('1')
			max_b = max(max_b, 7 - y)
			min_b = min(min_b, 7 - y)
		print(min_b, max_b)
	else:
		print('invalid')


def countSetBits(n):
	count = 0
	while n:
		count += n & 1
		n >>= 1
	return count
for _ in range(int(input())):
	la = []
	lb = []
	masks = [63, 6, 91, 79, 102, 109, 125, 7, 127, 111]
	conf = []
	for o in range(int(input())):
		(n, k) = list(map(int, input().split()))
		la.append(n)
		lb.append(k)
	q = len(la)
	for i in range(128):
		f = 1
		for j in range(q):
			if countSetBits(masks[la[j]] & i) != lb[j]:
				f = 0
				break
		if f:
			conf.append(i)
	k = max(lb)
	mi = 999
	ma = -999
	if len(conf) > 0:
		for u in conf:
			p = 7 - countSetBits(u)
			mi = min(mi, p)
			ma = max(ma, p)
		print(mi, ma)
	else:
		print('invalid')


from itertools import combinations

def solve(tests):
	for i in tests:
		if len(i[0]) < i[1]:
			print('invalid')
			return
	i = 0
	(mini, maxi) = (-1, 8)
	flag = True
	while mini <= i <= maxi:
		for s in combinations(range(7), i):
			for j in tests:
				if len(j[0] & set(s)) != j[1]:
					break
			else:
				if flag:
					flag = False
					mini = i
					i = 8
					break
				else:
					maxi = i
					print(7 - maxi, 7 - mini)
					return
		if flag:
			i += 1
		else:
			i -= 1
	if mini < 0:
		print('invalid')
for _ in range(int(input())):
	tests = []
	for _ in range(int(input())):
		(x, y) = map(int, input().split())
		if x == 0:
			tests.append(({0, 1, 2, 4, 5, 6}, y))
		elif x == 1:
			tests.append(({2, 5}, y))
		elif x == 2:
			tests.append(({0, 2, 3, 4, 6}, y))
		elif x == 3:
			tests.append(({0, 2, 3, 5, 6}, y))
		elif x == 4:
			tests.append(({1, 2, 3, 5}, y))
		elif x == 5:
			tests.append(({0, 1, 3, 5, 6}, y))
		elif x == 6:
			tests.append(({0, 1, 3, 4, 5, 6}, y))
		elif x == 7:
			tests.append(({0, 2, 5}, y))
		elif x == 8:
			tests.append(({0, 1, 2, 3, 4, 5, 6}, y))
		elif x == 9:
			tests.append(({0, 1, 2, 3, 5, 6}, y))
	solve(tests)


d = [[0, 3, 4, 2, 6, 5], [5, 6], [0, 5, 1, 4, 2], [0, 5, 1, 6, 2], [3, 1, 5, 6], [0, 3, 1, 6, 2], [0, 3, 4, 2, 6, 1], [0, 5, 6], [0, 1, 2, 3, 4, 5, 6], [0, 3, 1, 5, 6, 2]]

def check(ar, b):
	for i in ar:
		c = 0
		for j in d[i[0]]:
			if b[j]:
				c = c + 1
		if c != i[1]:
			return False
	return True
t = int(input())
while t:
	n = int(input())
	ar = [list(map(int, input().split())) for i in range(n)]
	v = 0
	mi = 8
	ma = 0
	for i in range(2 ** 7):
		b = [int(j) for j in bin(i)[2:]]
		while len(b) < 7:
			b = [0] + b
		if check(ar, b):
			v = 1
			mi = min(mi, b.count(0))
			ma = max(ma, b.count(0))
	if v:
		print(str(mi) + ' ' + str(ma))
	else:
		print('invalid')
	t = t - 1


sevseg = [126, 48, 109, 121, 51, 91, 95, 112, 127, 123]
for _ in range(int(input())):
	n = int(input())
	(x, y) = ([None] * n, [None] * n)
	mini = 8
	maxi = -1
	for i in range(n):
		(x[i], y[i]) = map(int, input().rstrip().split())
	badaflag = 0
	for check in range(128):
		flag = 1
		for i in range(n):
			if bin(sevseg[x[i]] & check).count('1') != y[i]:
				flag = 0
				break
		if flag:
			deadCell = 7 - bin(check).count('1')
			mini = min(mini, deadCell)
			maxi = max(maxi, deadCell)
			badaflag = 1
	if badaflag:
		print(mini, maxi)
	else:
		print('invalid')


from itertools import combinations

def solve(tests):
	(min_ans, max_ans) = (-1, -1)
	for test in tests:
		if len(test[0]) < test[1]:
			print('invalid')
			return
	i = 0
	looking_for_min = True
	while min_ans < i <= 7:
		for s in combinations(range(7), i):
			for test in tests:
				if len(test[0] & set(s)) != test[1]:
					break
			else:
				if looking_for_min:
					min_ans = i
					looking_for_min = False
					i = 7
					break
				else:
					max_ans = i
					print('%d %d' % (7 - max_ans, 7 - min_ans))
					return
		else:
			if looking_for_min:
				i += 1
			else:
				i -= 1
	if min_ans == -1:
		print('invalid')
	else:
		print('%d %d' % (7 - min_ans, 7 - min_ans))

def main():
	for _ in range(int(input())):
		tests = []
		for _ in range(int(input())):
			(x, y) = map(int, input().split())
			if x == 0:
				tests.append(({0, 1, 2, 4, 5, 6}, y))
			elif x == 1:
				tests.append(({2, 5}, y))
			elif x == 2:
				tests.append(({0, 2, 3, 4, 6}, y))
			elif x == 3:
				tests.append(({0, 2, 3, 5, 6}, y))
			elif x == 4:
				tests.append(({1, 2, 3, 5}, y))
			elif x == 5:
				tests.append(({0, 1, 3, 5, 6}, y))
			elif x == 6:
				tests.append(({0, 1, 3, 4, 5, 6}, y))
			elif x == 7:
				tests.append(({0, 2, 5}, y))
			elif x == 8:
				tests.append(({0, 1, 2, 3, 4, 5, 6}, y))
			elif x == 9:
				tests.append(({0, 1, 2, 3, 5, 6}, y))
		solve(tests)
main()


t = int(input())
segment_map = [(True, True, True, False, True, True, True), (False, False, True, False, False, True, False), (True, False, True, True, True, False, True), (True, False, True, True, False, True, True), (False, True, True, True, False, True, False), (True, True, False, True, False, True, True), (True, True, False, True, True, True, True), (True, False, True, False, False, True, False), (True, True, True, True, True, True, True), (True, True, True, True, False, True, True)]

def satisfies_all(configuration, constrains):
	for (number, count) in constrains:
		min_count = max_count = 0
		for (a, b) in zip(configuration, segment_map[number]):
			if not b:
				continue
			if a is None:
				max_count += 1
			elif a:
				min_count += 1
				max_count += 1
		if min_count > count or max_count < count:
			return False
	return True

def configuration_step_satisfied(config):
	try:
		i = config.index(None)
		config[i] = False
	except ValueError:
		configuration_step_not_satisfied(config)

def configuration_step_not_satisfied(config):
	i = 6 - config[::-1].index(False)
	config[i] = True
	config[i + 1:] = [None] * (6 - i)

def print_config(c):
	print(c)
	print('.{0}{0}{0}.\n{1}   {2}\n{1}   {2}\n{1}   {2}\n.{3}{3}{3}.\n{4}   {5}\n{4}   {5}\n{4}   {5}\n.{6}{6}{6}.\n'.format('-' if c[0] else ' ', '|' if c[1] else ' ', '|' if c[2] else ' ', '-' if c[3] else ' ', '|' if c[4] else ' ', '|' if c[5] else ' ', '-' if c[6] else ' '))
for _ in range(t):
	max_w = -9
	min_w = 9
	n = int(input())
	constrains = [None] * n
	for i in range(n):
		(x, y) = map(int, input().split())
		constrains[i] = (x, y)
	configuration = [None] * 7
	while not all(configuration):
		if satisfies_all(configuration, constrains):
			if all((x is not None for x in configuration)):
				working = 7 - sum(configuration)
				max_w = max(max_w, working)
				min_w = min(min_w, working)
			configuration_step_satisfied(configuration)
		else:
			try:
				configuration_step_not_satisfied(configuration)
			except ValueError:
				break
	if satisfies_all(configuration, constrains):
		working = 7 - sum(configuration)
		max_w = max(max_w, working)
		min_w = min(min_w, working)
	if max_w == -9:
		print('invalid')
	else:
		print(min_w, max_w)


import io, sys, atexit, os
import math as ma
from sys import exit
from decimal import Decimal as dec
from itertools import permutations
from itertools import combinations

def li():
	return list(map(int, input().split()))

def num():
	return map(int, input().split())

def nu():
	return int(input())

def find_gcd(x, y):
	while y:
		(x, y) = (y, x % y)
	return x

def rSubset(arr, r):
	return list(combinations(arr, r))
mm = 1000000007

def solve():
	t = nu()
	xp = [[1, 2, 3, 4, 5, 6], [2, 3], [1, 2, 7, 5, 4], [1, 2, 3, 4, 7], [2, 3, 6, 7], [1, 6, 7, 3, 4], [1, 3, 4, 5, 6, 7], [1, 2, 3], [1, 2, 3, 4, 5, 6, 7], [1, 2, 3, 4, 6, 7]]
	comb = [0]
	fp = [1, 2, 3, 4, 5, 6, 7]
	for i in range(1, 8):
		comb.append(rSubset(fp, i))
	for it in range(t):
		n = nu()
		fl = True
		kp = [-1] * 10
		ind = -1
		all = True
		for i in range(n):
			(x, y) = num()
			if len(xp[x]) < y:
				fl = False
			if len(xp[x]) != y:
				all = False
			kp[x] = y
			ind = x
		if fl == False:
			print('invalid')
			continue
		mx = 0
		mn = 0
		xom = False
		if all:
			mx = 0
			mn = 0
		else:
			mx = 0
			mn = 99
		for i in range(1, 8):
			for j in range(len(comb[i])):
				gh = comb[i][j]
				osd = [0] * 8
				for iq in gh:
					osd[iq] = 1
				vl = True
				for ko in range(10):
					if kp[ko] == -1:
						continue
					fg = kp[ko]
					for jg in range(len(xp[ko])):
						if osd[xp[ko][jg]] == 0:
							fg -= 1
					if fg != 0:
						vl = False
				if vl == True:
					xom = True
					mx = max(i, mx)
					mn = min(mn, i)
		if xom == True or all == True:
			print(mn, mx)
		else:
			print('invalid')
solve()


m = []
onesarr = []
for i in range(128):
	a = []
	ones = 0
	for j in range(7):
		l = i % 2 ** (7 - j) // 2 ** (6 - j)
		a.append(l)
		ones += l
	onesarr.append(7 - ones)
	m.append(a)
t = int(input())
for _ in range(t):
	poslag = True
	n = int(input())
	maxd = 0
	mind = 8
	arr = [8] * 10
	numbers = [[0, 1, 2, 3, 5, 6], [2, 5], [1, 2, 3, 4, 6], [1, 2, 4, 5, 6], [0, 2, 4, 5], [0, 1, 4, 5, 6], [0, 1, 3, 4, 5, 6], [1, 2, 5], [0, 1, 2, 3, 4, 5, 6], [0, 1, 2, 4, 5, 6]]
	for _ in range(n):
		(x, y) = [int(i) for i in input().split()]
		arr[x] = y
	for i in range(128):
		posflag = True
		for j in range(10):
			if arr[j] != 8:
				ch = 0
				for k in numbers[j]:
					ch += m[i][k]
				if ch != arr[j]:
					posflag = False
					break
		if posflag:
			mind = min(mind, onesarr[i])
			maxd = max(maxd, onesarr[i])
	if mind == 8:
		print('invalid')
	else:
		print(mind, maxd)


digits = [119, 18, 93, 91, 58, 107, 111, 82, 127, 123]
t = int(input())
for ti in range(t):
	n = int(input())
	(x, y) = ([None for _ in range(n)], [None for _ in range(n)])
	for i in range(n):
		(x[i], y[i]) = map(int, input().split())
	any_ok = False
	(min_dead, max_dead) = (7, 0)
	for mask in range(1 << 7):
		ok = True
		for i in range(n):
			if bin(digits[x[i]] & mask).count('1') != y[i]:
				ok = False
		if ok:
			any_ok = True
			num_dead = 7 - bin(mask).count('1')
			min_dead = min(min_dead, num_dead)
			max_dead = max(max_dead, num_dead)
	if any_ok:
		print(min_dead, max_dead)
	else:
		print('invalid')