import re


rules = {}
msgs = []
with open('input.txt') as fh:
	for line in fh:
		line = line.rstrip()
		if ': ' in line:
			key, value = line.split(': ')
			rules[key] = value
		elif line:
			msgs.append(line)


def re_compile(rules, key='0'):
	compiled = {}

	def c(part):
		s = ''
		for c in part.split():
			if c[0] == '"':
				s += c.strip('"')
			else:
				s += get(c)
		return s

	def get(i):
		if i not in compiled:
			parts = [c(p) for p in rules[i].split(' | ')]
			if len(parts) > 1:
				compiled[i] = '(%s)' % '|'.join(parts)
			else:
				compiled[i] = parts[0]
		return compiled[i]

	return get(key)


def is_match2(msg, pattern42, pattern31):
	# 0: 8 11
	# 8: 42 | 42 8  (42+)
	# 11: 42 31 | 42 11 31  (42{n} 31{n})
	#
	# This means 0: 42{a} 31{b} with a > b > 0
	MAX_ITERATIONS = 20
	if not re.match('(%s)+(%s)+$' % (pattern42, pattern31), msg):
		return False
	for b in range(1, MAX_ITERATIONS):
		for a in range(b + 1, MAX_ITERATIONS):
			if re.match('(%s){%i}(%s){%i}$' % (pattern42, a, pattern31, b), msg):
				return True
	return False

pattern1 = re.compile(re_compile(rules) + '$')
print(len([msg for msg in msgs if pattern1.match(msg)]))

count2 = 0
pattern42 = re_compile(rules, '42')
pattern31 = re_compile(rules, '31')
for msg in msgs:
	if is_match2(msg, pattern42, pattern31):
		count2 += 1
print(count2)