Alice and Bob created $N$ and $M$ recipes, respectively ($N, M \ge 1$), and submitted them to Chef for evaluation. Each recipe is represented by a string containing only lowercase English letters. Let's denote Alice's recipes by $A_1, A_2, \ldots, A_N$ and Bob's recipes by $B_1, B_2, \ldots, B_M$.
Accidentally, Chef mixed up those recipes ― now, he has $L = N+M$ recipes in a sequence $S_1, S_2, \ldots, S_L$. Thankfully, the recipes created by Alice and Bob are distinguishable from each other. It is well-known that for each recipe $s$ created by Alice, the following property holds, and for each recipe created by Bob, it does not hold: For each $1 \le l < r \le |s|$, the substring $s_l, s_{l+1}, \ldots, s_r$ contains at least as many vowels as consonants. The letters 'a', 'e', 'i', 'o', 'u' are vowels, while the other letters are consonants.
The score of a candidate who made $K$ recipes is calculated as the product of $\frac{x_c}{fx_c^K}$ for all letters $c$ that occur in at least one of these recipes; here, $x_c$ is the number of recipes which contain the letter $c$ and $fx_c$ is the total number of occurrences of this letter in all $K$ recipes.
Let's denote the scores of Alice and Bob by $sc_A$ and $sc_B$ respectively. Chef wants to know their ratio $sc_A/sc_B$. We know that Chef is a legendary cook, but he is not very good at calculating, so he is asking you to find that number.

-----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 $L$.
- $L$ lines follow. For each valid $i$, the $i$-th of these lines contains a single string $S_i$.

-----Output-----
For each test case, if the ratio of scores exceeds $10^7$, print a single line containing the string "Infinity" (without quotes); otherwise, print a single line containing one real number $sc_A/sc_B$.
Your answer will be considered correct if its absolute or relative error does not exceed $10^{-6}$. It is guaranteed that $sc_A/sc_B$ does not lie in the range $10^7 \pm 10$.

-----Constraints-----
- $1 \le T \le 10^5$
- $2 \le L \le 10^5$
- $2 \le |S_i| \le 10^5$ for each valid $i$
- for each valid $i$, $S_i$ contains only lowercase English letters
- the sum of $|S_1| + |S_2| + \ldots + |S_L|$ over all test cases does not exceed $10^7$

-----Subtasks-----
Subtask #1 (25 points):
- $L \le 10$
- $|S_i| \le 10$ for each valid $i$
Subtask #2 (75 points): original constraints

-----Example Input-----
2
4
aba
abc
bab
aac
3
aba
baab
abc

-----Example Output-----
1.1250000
0.0277778

-----Explanation-----
Example case 1: The recipes "aba" and "aac" are created by Alice, while the recipes "abc" and "bab" are created by Bob. The scores are:
- $sc_A = \frac{x_a}{fx_a^N} \cdot \frac{x_b}{fx_b^N} \cdot \frac{x_c}{fx_c^N} = \frac{2}{4^2} \cdot \frac{1}{1^2} \cdot \frac{1}{1^2} = \frac{1}{8}$
- $sc_B = \frac{x_a}{fx_a^M} \cdot \frac{x_b}{fx_b^M} \cdot \frac{x_c}{fx_c^M} = \frac{2}{2^2} \cdot \frac{2}{3^2} \cdot \frac{1}{1^2} = \frac{1}{9}$
- $\frac{sc_A}{sc_B} = \frac{1/8}{1/9} = 1.125$

Source: codechef | Difficulty: HARD
Tags: Number theory

Data structures

Mathematics

String algorithms


Solutions:
import time
import math
import random
import string

def log2(x):
	return math.log(x, 2)
MAX = log2(10000000.0)
MIN = log2(1e-07)
start_time = time.time()
vowels = 'aeiou'
v = {'a': 1, 'e': 1, 'i': 1, 'o': 1, 'u': 1}
abets = string.ascii_lowercase
tcs = int(input())
for test in range(tcs):
	l = int(input())
	a = []
	b = []
	for wer in range(l):
		s = input()
		n = len(s)
		c1 = 0
		for i in range(n):
			if s[i] not in v:
				if i + 1 < n:
					if s[i + 1] not in v:
						c1 = 1
						break
				if i + 2 < n:
					if s[i + 2] not in v:
						c1 = 1
						break
		if c1 == 1:
			b.append(s)
		else:
			a.append(s)
	alen = len(a)
	blen = len(b)
	achar_dict = {}
	atotal_dict = {}
	for recipe in a:
		d = {}
		for ch in recipe:
			d[ch] = 1
			if atotal_dict.get(ch):
				atotal_dict[ch] += 1
			else:
				atotal_dict[ch] = 1
		for ch in d:
			if achar_dict.get(ch):
				achar_dict[ch] += 1
			else:
				achar_dict[ch] = 1
	bchar_dict = {}
	btotal_dict = {}
	for recipe in b:
		d = {}
		for ch in recipe:
			d[ch] = 1
			if btotal_dict.get(ch):
				btotal_dict[ch] += 1
			else:
				btotal_dict[ch] = 1
		for ch in d:
			if bchar_dict.get(ch):
				bchar_dict[ch] += 1
			else:
				bchar_dict[ch] = 1
	result = 0
	for i in achar_dict:
		result += log2(achar_dict[i]) - alen * log2(atotal_dict[i])
	for i in bchar_dict:
		result += blen * log2(btotal_dict[i]) - log2(bchar_dict[i])
	if result > MAX:
		print('Infinity')
	elif result < MIN:
		print(0)
	else:
		print(2 ** result)


vowels = ['a', 'e', 'i', 'o', 'u']
letters = 'qwertyuiopasdfghjklzxcvbnm'
t = int(input())
for _ in range(t):
	alice = []
	bob = []
	n = int(input())
	for l in range(n):
		arr = input()
		if len(arr) == 2:
			if arr[0] in vowels or arr[1] in vowels:
				alice.append(arr)
			else:
				bob.append(arr)
		else:
			flag2 = 0
			for i in range(len(arr) - 2):
				if not (arr[i] in vowels and arr[i + 1] in vowels or (arr[i + 1] in vowels and arr[i + 2] in vowels) or (arr[i] in vowels and arr[i + 2] in vowels)):
					flag2 = 1
					bob.append(arr)
					break
			if flag2 == 0:
				alice.append(arr)
	alice_total = ''.join(alice)
	bob_total = ''.join(bob)
	alice_d = 1
	alice_n = 1
	bob_d = 1
	bob_n = 1
	for letter in letters:
		if letter in alice_total:
			alice_count = 0
			alice_d *= alice_total.count(letter)
			for word in alice:
				if letter in word:
					alice_count += 1
			alice_n *= alice_count
		if letter in bob_total:
			bob_count = 0
			bob_d *= bob_total.count(letter)
			for word in bob:
				if letter in word:
					bob_count += 1
			bob_n *= bob_count
	mini = min(len(bob), len(alice))
	bob_d = bob_d ** (len(bob) / mini)
	alice_d = alice_d ** (len(alice) / mini)
	x = alice_n / bob_n
	for i in range(mini):
		x *= bob_d / alice_d
	if x <= 10 ** 7:
		print(x)
	else:
		print('Infinity')


vowles = ['a', 'e', 'i', 'o', 'u']

def diction(i):
	d = {}
	for j in i:
		if j not in d:
			d[j] = 0
		d[j] += 1
	return d

def check1(i):
	a = 0
	b = 0
	if len(i) == 2:
		if i[0] not in vowles and i[1] not in vowles:
			return 0
	else:
		for j in range(1, len(i) - 1):
			if i[j] not in vowles:
				if i[j + 1] not in vowles:
					return 0
				if i[j - 1] not in vowles:
					return 0
			elif i[j + 1] not in vowles and i[j - 1] not in vowles:
				return 0
	return 1

def check(i, a):
	p = 0
	for j in a:
		if i in j:
			p += 1
	return p
t = int(input())
while t > 0:
	t -= 1
	n = int(input())
	alice = []
	bob = []
	for i in range(n):
		b = input()
		a = check1(b)
		if a == 1:
			alice.append(b)
		else:
			bob.append(b)
	N = len(alice)
	M = len(bob)
	a = ''.join(alice)
	b = ''.join(bob)
	d1 = diction(a)
	d2 = diction(b)
	res1 = 1
	res2 = 1
	for i in d1:
		p1 = check(i, alice)
		res1 *= p1
		res2 *= d1[i]
	res3 = 1
	res4 = 1
	for i in d2:
		p1 = check(i, bob)
		res3 *= p1
		res4 *= d2[i]
	if res2 == res4:
		res5 = pow(res4, M - N)
	elif M == N:
		if res2 != 0:
			res5 = res4 / res2
			res5 = pow(res5, M)
	else:
		temp1 = 0
		temp2 = 0
		if M % 2 == 0:
			temp1 = pow(res4, M // 2)
		else:
			temp1 = pow(res4, M // 2 + 1)
		if N % 2 == 0:
			temp2 = pow(res2, N // 2)
		else:
			temp2 = pow(res2, N // 2 + 1)
		res5 = temp1 / temp2
		res5 *= res5
		if M % 2 != 0:
			res5 = res5 / res4
		if N % 2 != 0:
			res5 = res5 * res2
	calc = res1 / res3 * res5
	if calc > 10 ** 7:
		print('Infinity')
	else:
		print('%.10f' % calc)


def printf(a):
	print(a)

def enter_int():
	a = int(input())
	return a

def enter_str():
	a = input()
	return a
v = ['a', 'e', 'i', 'o', 'u']
for _ in range(enter_int()):
	n = enter_int()
	(a, b) = ([], [])
	for i in range(n):
		s = enter_str()
		isa = True
		for j in range(1, len(s) - 1):
			if s[j] in v:
				if s[j - 1] not in v and s[j + 1] not in v:
					isa = False
			elif s[j - 1] not in v or s[j + 1] not in v:
				isa = False
			if not isa:
				break
		if s[0] not in v and s[1] not in v:
			isa = False
		if s[-1] not in v and s[-2] not in v:
			isa = False
		if isa:
			a.append(s)
		else:
			b.append(s)
	(dicta, dictb) = ({}, {})
	for i in a:
		freq = {}
		for j in i:
			if j in freq:
				freq[j] += 1
			else:
				freq[j] = 1
		for j in freq:
			if j not in dicta:
				dicta[j] = (1, freq[j])
			else:
				dicta[j] = (dicta[j][0] + 1, dicta[j][1] + freq[j])
	for i in b:
		freq = {}
		for j in i:
			if j in freq:
				freq[j] += 1
			else:
				freq[j] = 1
		for j in freq:
			if j not in dictb:
				dictb[j] = (1, freq[j])
			else:
				dictb[j] = (dictb[j][0] + 1, dictb[j][1] + freq[j])
	ans = 1
	for i in dicta:
		ans *= dicta[i][0]
	for i in dictb:
		ans /= dictb[i][0]
	(x, y) = (1, 1)
	for i in dictb:
		x *= dictb[i][1]
	for i in dicta:
		y *= dicta[i][1]
	(alice, bob) = (len(a), len(b))
	for i in range(bob):
		while alice > 0 and ans > 10 ** 7:
			ans /= y
			alice -= 1
		ans *= x
		if ans > 10 ** 7 and alice == 0:
			break
	while alice > 0:
		ans /= y
		if ans < 1 and alice > 100:
			ans = 0
			break
		alice -= 1
	if ans > 10 ** 7:
		printf('Infinity')
	else:
		printf(ans)


import math
import os
import random
import re
import sys
from math import log

def isVowel(char):
	return char in ['a', 'e', 'i', 'o', 'u']

def isA(string):
	for i in range(len(string)):
		if not isVowel(string[i]) and (i + 1 < len(string) and (not isVowel(string[i + 1])) or (i + 2 < len(string) and (not isVowel(string[i + 2])))):
			return False
	return True

def f(arr):
	a = []
	b = []
	aRecipes = {}
	aAppearances = {}
	bRecipes = {}
	bAppearances = {}
	for i in arr:
		if isA(i):
			a.append(i)
		else:
			b.append(i)
	for i in range(len(a)):
		for j in a[i]:
			if j not in aAppearances:
				aAppearances[j] = 0
			aAppearances[j] += 1
			if j not in aRecipes:
				aRecipes[j] = {}
			aRecipes[j][i] = 1
	totalA = 0
	for i in aAppearances:
		totalA += log(len(aRecipes[i]), 10) - log(aAppearances[i], 10) * len(a)
	for i in range(len(b)):
		for j in b[i]:
			if j not in bAppearances:
				bAppearances[j] = 0
			bAppearances[j] += 1
			if j not in bRecipes:
				bRecipes[j] = {}
			bRecipes[j][i] = 1
	totalB = 0
	for i in bAppearances:
		totalB += log(len(bRecipes[i]), 10) - log(bAppearances[i], 10) * len(b)
	if totalA - totalB > 7:
		return 'Infinity'
	if totalB - totalA > 7:
		return 0
	return 10 ** (totalA - totalB)
t = int(input())
for i in range(t):
	l = int(input())
	arr = []
	for j in range(l):
		arr.append(input())
	result = f(arr)
	print(result)


from math import log10

def identify_vowel(recipe):
	return [1 if char in {'a', 'e', 'i', 'o', 'u'} else 0 for char in recipe]

def identify(s):
	vow = identify_vowel(s)
	if len(vow) <= 2:
		return sum(vow) >= 1
	pre_s = vow[0] + vow[1]
	for i in range(2, len(s)):
		pre_s += vow[i]
		if pre_s < 2:
			return False
		pre_s -= vow[i - 2]
	return True

def calculate(recipes):
	K = len(recipes)
	occurences = {}
	exist = {}
	for i in range(len(recipes)):
		recipe = recipes[i]
		for s in recipe:
			if not s in occurences:
				occurences[s] = 0
			if not s in exist:
				exist[s] = set()
			occurences[s] += 1
			exist[s].add(i)
	score = 0
	for alphabet in exist.keys():
		score += log10(len(exist[alphabet])) - K * log10(occurences[alphabet])
	return score
test = int(input())
while test > 0:
	test -= 1
	l = int(input())
	alice = []
	bob = []
	for i in range(l):
		s = input()
		if identify(s):
			alice.append(s)
		else:
			bob.append(s)
	ans = calculate(alice) - calculate(bob)
	if ans > 7:
		print('Infinity')
	else:
		ans = 10 ** ans
		print(ans)


import math

def check(s):
	vowels = 'aeiou'
	(cnt_vowel, cnt_consonant) = (0, 0)
	for i in range(len(s)):
		flag = s[i] not in vowels
		if i and flag:
			if cnt_consonant > 0:
				if cnt_vowel <= 1:
					return False
				else:
					(cnt_consonant, cnt_vowel) = (0, 0)
			cnt_vowel = 0
		cnt_vowel += int(not flag)
		cnt_consonant += int(flag)
	return True

def getAns(v):
	(cnt, cnt_char) = (dict(), dict())
	for x in v:
		s = set()
		for y in x:
			cnt_char[y] = cnt_char.get(y, 0) + 1
			if y not in s:
				cnt[y] = cnt.get(y, 0) + 1
				s.add(y)
	total_char = len(v)
	ans = 0
	for (x, y) in cnt_char.items():
		ans += math.log10(cnt[x]) - total_char * math.log10(y)
	return ans
t = int(input())
for _ in range(t):
	n = int(input())
	(v1, v2) = ([], [])
	for i in range(n):
		s = input()
		if check(s):
			v1.append(s)
		else:
			v2.append(s)
	d1 = getAns(v1)
	d2 = getAns(v2)
	d1 -= d2
	if d1 >= 7:
		print('Infinity')
	else:
		ans = 10 ** d1
		print('%.15f' % ans)


import math
import decimal
decimal.getcontext().prec = 1000
t = int(input())
for _ in range(t):
	l = int(input())
	alice = []
	bob = []
	alice_all = ''
	bob_all = ''
	vowels = ['a', 'e', 'i', 'o', 'u']
	for i in range(l):
		temp = input()
		consonant_index = -1
		for j in range(len(temp)):
			if temp[j] in vowels:
				continue
			elif consonant_index == -1:
				consonant_index = j
			elif j - consonant_index <= 2:
				bob.append(temp)
				bob_all = bob_all + temp
				break
			else:
				consonant_index = j
		else:
			alice.append(temp)
			alice_all = alice_all + temp
	if l <= 10:
		n = len(alice)
		m = len(bob)
		(score_A, score_B) = (1, 1)
		(x_a, x_b) = (1, 1)
		(fx_a, fx_b) = (1, 1)
		for i in range(97, 123):
			char = chr(i)
			if char in alice_all:
				rec_a = [x for x in alice if char in x]
				x_a *= len(rec_a)
				fx_a = fx_a * alice_all.count(char)
			if char in bob_all:
				rec_b = [x for x in bob if char in x]
				x_b *= len(rec_b)
				fx_b = fx_b * bob_all.count(char)
		fx_a = math.pow(fx_a, n)
		fx_b = math.pow(fx_b, m)
		score_A = x_a / fx_a
		score_B = x_b / fx_b
		ans = score_A / score_B
		if ans > 10000000:
			print('Infinity')
		else:
			print('{0:.9f}'.format(ans))
	else:
		n = decimal.Decimal(len(alice))
		m = decimal.Decimal(len(bob))
		score_A = decimal.Decimal(1).quantize(decimal.Decimal('0.0000000001'))
		score_B = decimal.Decimal(1).quantize(decimal.Decimal('0.0000000001'))
		x_a = decimal.Decimal(1).quantize(decimal.Decimal('0.0000000001'))
		x_b = decimal.Decimal(1).quantize(decimal.Decimal('0.0000000001'))
		power_a = decimal.Decimal(1).quantize(decimal.Decimal('0.0000000001'))
		power_b = decimal.Decimal(1).quantize(decimal.Decimal('0.0000000001'))
		fx_a = decimal.Decimal(1).quantize(decimal.Decimal('0.0000000001'))
		fx_b = decimal.Decimal(1).quantize(decimal.Decimal('0.0000000001'))
		ans = decimal.Decimal(1).quantize(decimal.Decimal('0.0000000001'))
		charInA = ''.join(sorted(set(alice_all)))
		charInB = ''.join(sorted(set(bob_all)))
		ctx = decimal.getcontext().copy()
		ctx.Emax = decimal.MAX_EMAX
		ctx.Emin = decimal.MIN_EMIN
		ctx.prec = 10000
		for i in charInA:
			rec_a = [x for x in alice if i in x]
			if len(rec_a) > 0:
				x_a = ctx.multiply(x_a, len(rec_a))
				fx_a = ctx.multiply(fx_a, alice_all.count(i))
		for i in charInB:
			rec_b = [x for x in bob if i in x]
			if len(rec_b) > 0:
				x_b = ctx.multiply(x_b, len(rec_b))
				fx_b = ctx.multiply(fx_b, bob_all.count(i))
		denom_a = ctx.power(fx_a, n)
		denom_b = ctx.power(fx_b, m)
		score_A = ctx.divide(x_a, denom_a)
		score_B = ctx.divide(x_b, denom_b)
		ans = ctx.divide(score_A, score_B)
		if ans > 10000000:
			print('Infinity')
		else:
			print('{0:.9f}'.format(ans))


import math
import re
wr1 = re.compile('[^aeiou][aeiou][^aeiou]')
wr2 = re.compile('[^aeiou][^aeiou]')

def isAlice(word):
	if wr1.search(word) or wr2.search(word):
		return False
	else:
		return True

def occCount(word, D1, D2):
	m = set()
	for lett in word:
		if lett in D1:
			D1[lett] += 1
		else:
			D1[lett] = 1
		if lett not in m:
			if lett in D2:
				D2[lett] += 1
			else:
				D2[lett] = 1
		m.add(lett)
	return (D1, D2)

def calculate(L):
	alice_occ = dict()
	alice_recepie_count = dict()
	bob_occ = dict()
	bob_recepie_count = dict()
	alice = bob = 0
	for word in L:
		if isAlice(word):
			alice += 1
			(alice_occ, alice_recepie_count) = occCount(word, alice_occ, alice_recepie_count)
		else:
			bob += 1
			(bob_occ, bob_recepie_count) = occCount(word, bob_occ, bob_recepie_count)
	A = B = 0
	for occ in alice_recepie_count.keys():
		A += math.log10(alice_recepie_count[occ]) - alice * math.log10(alice_occ[occ])
	for occ in bob_recepie_count.keys():
		B += math.log10(bob_recepie_count[occ]) - bob * math.log10(bob_occ[occ])
	ans = A - B
	return 'Infinity' if ans > 7 else math.pow(10, ans)
for _ in range(int(input())):
	L = []
	for _ in range(int(input())):
		L.append(input())
	print(calculate(L))


import math
import os
import random
import re
import sys
from math import log

def isVowel(char):
	return char in ['a', 'e', 'i', 'o', 'u']

def isA(string):
	for i in range(len(string)):
		if not isVowel(string[i]) and (i + 1 < len(string) and (not isVowel(string[i + 1])) or (i + 2 < len(string) and (not isVowel(string[i + 2])))):
			return False
	return True

def f(arr):
	a = []
	b = []
	aRecipes = {}
	aAppearances = {}
	bRecipes = {}
	bAppearances = {}
	for i in arr:
		if isA(i):
			a.append(i)
		else:
			b.append(i)
	for i in range(len(a)):
		for j in a[i]:
			if j not in aAppearances:
				aAppearances[j] = 0
			aAppearances[j] += 1
			if j not in aRecipes:
				aRecipes[j] = {}
			aRecipes[j][i] = 1
	for i in range(len(b)):
		for j in b[i]:
			if j not in bAppearances:
				bAppearances[j] = 0
			bAppearances[j] += 1
			if j not in bRecipes:
				bRecipes[j] = {}
			bRecipes[j][i] = 1
	total = 0
	aKeys = list(aAppearances.keys())
	bKeys = list(bAppearances.keys())
	for i in range(max(len(aKeys), len(bKeys))):
		try:
			total += log(len(aRecipes[aKeys[i]]), 10) - log(aAppearances[aKeys[i]], 10) * len(a)
		except:
			pass
		try:
			total -= log(len(bRecipes[bKeys[i]]), 10) - log(bAppearances[bKeys[i]], 10) * len(b)
		except:
			pass
	if total > 7:
		return 'Infinity'
	if total < -7:
		return 0
	return '{0:.16f}'.format(10 ** total)
t = int(input())
for i in range(t):
	l = int(input())
	arr = []
	for j in range(l):
		arr.append(input())
	result = f(arr)
	print(str(result))


from math import log10

def f():
	n = int(input())
	alice = [0] * 150
	alicew = [0] * 150
	bob = [0] * 150
	bobw = [0] * 150
	ac = 0
	bc = 0
	al = 0
	bl = 0
	for i in range(n):
		a = input()
		flag = 0
		count = [0] * 150
		if len(a) == 2:
			if a[0] not in 'aeiou' and a[1] not in 'aeiou':
				flag = 1
		for i in range(0, len(a) - 1):
			if a[i] in 'bcdfghjklmnpqrstvwxyz':
				try:
					if a[i + 1] in 'bcdfghjklmnpqrstvwxyz' or a[i + 2] in 'bcdfghjklmnpqrstvwxyz':
						flag = 1
						break
				except IndexError:
					break
		if flag == 1:
			bc += 1
			for i in range(0, len(a)):
				bob[ord(a[i])] += 1
				count[ord(a[i])] += 1
			for i in range(ord('a'), ord('z') + 1):
				if count[i]:
					bobw[i] += 1
		else:
			ac += 1
			for i in range(0, len(a)):
				alice[ord(a[i])] += 1
				count[ord(a[i])] += 1
			for i in range(ord('a'), ord('z') + 1):
				if count[i]:
					alicew[i] += 1
	for i in range(ord('a'), ord('z') + 1):
		if alice[i]:
			al += log10(alicew[i]) - ac * log10(alice[i])
		if bob[i]:
			bl += log10(bobw[i]) - bc * log10(bob[i])
	if al - bl > 7:
		print('Infinity')
	else:
		print(10 ** (al - bl))
for i in range(int(input())):
	f()


from sys import stdin
z = ['a', 'i', 'e', 'o', 'u']
t = int(stdin.readline())
while t > 0:
	t -= 1
	n = int(stdin.readline())
	alice = []
	bob = []
	for j in range(n):
		s = str(stdin.readline().strip('\n'))
		isalice = True
		for i in range(1, len(s) - 1):
			if s[i] in z:
				if s[i - 1] not in z and s[i + 1] not in z:
					isalice = False
			elif s[i - 1] not in z or s[i + 1] not in z:
				isalice = False
			if not isalice:
				break
		if s[0] not in z and s[1] not in z:
			isalice = False
		if s[-1] not in z and s[-2] not in z:
			isalice = False
		if isalice:
			alice.append(s)
		else:
			bob.append(s)
	ali = {}
	bo = {}
	for i in alice:
		d = {}
		for j in i:
			if j in d:
				d[j] += 1
			else:
				d[j] = 1
		for j in d:
			if j not in ali:
				ali[j] = (1, d[j])
			else:
				ali[j] = (ali[j][0] + 1, ali[j][1] + d[j])
	for i in bob:
		d = {}
		for j in i:
			if j in d:
				d[j] += 1
			else:
				d[j] = 1
		for j in d:
			if j not in bo:
				bo[j] = (1, d[j])
			else:
				bo[j] = (bo[j][0] + 1, bo[j][1] + d[j])
	ans = 1
	for i in ali:
		ans *= ali[i][0]
	for i in bo:
		ans = ans / bo[i][0]
	x = 1
	y = 1
	for i in bo:
		x = x * bo[i][1]
	for i in ali:
		y = y * ali[i][1]
	alice = len(alice)
	bob = len(bob)
	for i in range(bob):
		while alice > 0 and ans > 10000000:
			ans = ans / y
			alice -= 1
		ans *= x
		if ans > 10000000 and alice == 0:
			break
	while alice > 0:
		ans = ans / y
		if ans < 1 and alice > 100:
			ans = 0
			break
		alice -= 1
	if ans > 10000000:
		print('Infinity')
	else:
		print(ans)


def partition(s):
	l = len(s)
	d = 'aeiou'
	for i in range(l):
		if i + 1 < l:
			if s[i] not in d and s[i + 1] not in d:
				return 0
		if i + 2 < l:
			if s[i] not in d and s[i + 2] not in d:
				return 0
	return 1
t = int(input())
while t != 0:
	t -= 1
	n = int(input())
	alice = []
	bob = []
	for i in range(n):
		s = input()
		if partition(s) == 1:
			alice.append(s)
		else:
			bob.append(s)
	alocc = [0] * 26
	bocc = [0] * 26
	alrow = [0] * 26
	bobrow = [0] * 26
	r = [0] * 26
	for i in range(len(alice)):
		a = alice[i]
		for j in range(len(a)):
			h = ord(a[j]) - ord('a')
			alocc[h] += 1
			if r[h] == 0:
				alrow[h] += 1
				r[h] = 1
		r = [0] * 26
	r = [0] * 26
	for i in range(len(bob)):
		b = bob[i]
		for j in range(len(b)):
			h = ord(b[j]) - ord('a')
			bocc[h] += 1
			if r[h] == 0:
				bobrow[h] += 1
				r[h] = 1
		r = [0] * 26
	numa = 1
	numb = 1
	dena = 1
	denb = 1
	for i in range(26):
		if alocc[i] != 0:
			numa = numa * alrow[i]
			dena = dena * alocc[i]
		if bocc[i] != 0:
			numb = numb * bobrow[i]
			denb = denb * bocc[i]
	n1 = len(alice)
	m = len(bob)
	den = 1
	if dena == denb:
		res = numa * pow(denb, m - n1) / numb
	elif m == n1:
		den = denb / dena
		res = numa * pow(den, m) / numb
	else:
		if m % 2 == 0:
			h = pow(denb, m // 2)
		else:
			h = pow(denb, m // 2 + 1)
		if n1 % 2 == 0:
			k = pow(dena, n1 // 2)
		else:
			k = pow(dena, n1 // 2 + 1)
		den = h / k
		den = den * den
		if m % 2 != 0:
			den = den / denb
		if n1 % 2 != 0:
			den = den * dena
		res = numa * den / numb
	if res > 10000000:
		print('Infinity')
	else:
		print('%.8f' % res)


from math import log10
import math
for _ in range(int(input())):
	n = int(input())
	alice = []
	bob = []
	words = []
	for i in range(n):
		words.append(input())
	for cur in words:
		prev = -1
		f = 0
		for j in range(len(cur)):
			if cur[j] not in ['a', 'e', 'i', 'o', 'u']:
				if prev == -1:
					prev = j
				elif abs(prev - j) == 2 or abs(prev - j) == 1:
					f = 1
					break
				else:
					prev = j
		if f == 1:
			bob.append(cur)
		else:
			alice.append(cur)
	n1 = len(alice)
	freq_a = {}
	for i in alice:
		for j in i:
			if j not in freq_a:
				freq_a[j] = 1
			else:
				freq_a[j] += 1
	num_a = {}
	for i in freq_a:
		num_a[i] = 0
		for j in alice:
			if i in j:
				num_a[i] += 1
	num1 = 1
	den1 = 1
	for i in num_a:
		num1 = num1 * num_a[i]
		den1 = den1 * freq_a[i]
	n2 = len(bob)
	freq_b = {}
	for i in bob:
		for j in i:
			if j not in freq_b:
				freq_b[j] = 1
			else:
				freq_b[j] += 1
	num_b = {}
	for i in freq_b:
		num_b[i] = 0
		for j in bob:
			if i in j:
				num_b[i] += 1
	num2 = 1
	den2 = 1
	for i in num_b:
		num2 = num2 * num_b[i]
		den2 = den2 * freq_b[i]
	ans1 = log10(num1) + n2 * log10(den2)
	ans2 = log10(num2) + n1 * log10(den1)
	ans1 = ans1 - ans2
	if ans1 > 7.0:
		print('Infinity')
	else:
		print(pow(10, ans1))


from collections import defaultdict
from heapq import *
import itertools, math, heapq

def parse_integer_list():
	return [int(x) for x in input().split()]
cons = {'v', 'w', 'f', 'z', 'd', 'k', 's', 'x', 'b', 'c', 't', 'm', 'p', 'q', 'y', 'j', 'n', 'r', 'l', 'h', 'g'}
vowels = {'u', 'o', 'e', 'i', 'a'}

def filter_string(s):
	for i in range(len(s) - 1):
		if s[i] in vowels:
			continue
		if i == len(s) - 2:
			if s[i + 1] in cons:
				return False
			break
		if s[i + 1] in cons or s[i + 2] in cons:
			return False
	return True
from collections import defaultdict

def handle_input(*args):
	a_index = ord('a')
	(L, S) = args
	A = []
	B = []
	for i in range(L):
		if filter_string(S[i]):
			A.append(S[i])
		else:
			B.append(S[i])
	a_letters = [(0, 0)] * 123
	b_letters = [(0, 0)] * 123
	for i in range(len(A)):
		used = [False] * 123
		for c in A[i]:
			x = a_letters[ord(c)]
			if used[ord(c)]:
				num = x[0]
			else:
				num = x[0] + 1
				used[ord(c)] = True
			a_letters[ord(c)] = (num, x[1] + 1)
	for i in range(len(B)):
		used = [False] * 123
		for c in B[i]:
			x = b_letters[ord(c)]
			if used[ord(c)]:
				num = x[0]
			else:
				num = x[0] + 1
				used[ord(c)] = True
			b_letters[ord(c)] = (num, x[1] + 1)
	a_score_top = 0
	a_score_bot = 0
	log_a = math.log(len(B))
	log_b = math.log(len(A))
	for x in a_letters:
		if x == (0, 0):
			continue
		a_score_top += math.log2(x[0])
		a_score_bot += math.log2(x[1]) * len(A)
	for x in b_letters:
		if x == (0, 0):
			continue
		a_score_bot += math.log2(x[0])
		a_score_top += math.log2(x[1]) * len(B)
	if a_score_top > 7 * math.log2(10) + a_score_bot:
		print('Infinity')
	else:
		print(pow(2, a_score_top - a_score_bot))
T = int(input())
for i in range(T):
	L = int(input())
	S = []
	for i in range(L):
		S.append(input().strip())
	handle_input(L, S)


import time
vowels = 'aeiou'
start_time = time.time()

def main():
	import math as m
	ryt = m.log(10 ** 7, 2)
	lyt = m.log(9e-07, 2)
	t = int(input())
	v = {'a': 1, 'e': 1, 'i': 1, 'o': 1, 'u': 1}
	for qwer in range(t):
		l = int(input())
		a = []
		b = []
		for wer in range(l):
			s = input()
			n = len(s)
			c1 = 0
			for i in range(n):
				if s[i] not in v:
					if i + 1 < n:
						if s[i + 1] not in v:
							c1 = 1
							break
					if i + 2 < n:
						if s[i + 2] not in v:
							c1 = 1
							break
			if c1 == 1:
				b.append(s)
			else:
				a.append(s)
		xa = {}
		fxa = {}
		xb = {}
		fxb = {}
		ka = len(a)
		kb = len(b)
		for i in range(ka):
			d = {}
			for j in range(len(a[i])):
				if a[i][j] in d:
					d[a[i][j]] += 1
				else:
					d[a[i][j]] = 1
			for u in d:
				if u in xa:
					xa[u] += 1
					fxa[u] += d[u]
				else:
					xa[u] = 1
					fxa[u] = d[u]
		for i1 in range(kb):
			d = {}
			for j1 in range(len(b[i1])):
				if b[i1][j1] in d:
					d[b[i1][j1]] += 1
				else:
					d[b[i1][j1]] = 1
			for u1 in d:
				if u1 in xb:
					xb[u1] += 1
					fxb[u1] += d[u1]
				else:
					xb[u1] = 1
					fxb[u1] = d[u1]
		ans = 0
		for y in xa:
			ans += m.log(xa[y], 2) - ka * m.log(fxa[y], 2)
		for r in xb:
			ans += kb * m.log(fxb[r], 2) - m.log(xb[r], 2)
		if ans > ryt:
			print('Infinity')
		elif ans < lyt:
			print(0)
		else:
			print(2 ** ans)
main()


import math

def score(a):
	count = {}
	recipes = {}
	for i in range(len(a)):
		x = a[i]
		for j in range(len(x)):
			if x[j] in count:
				count[x[j]] += 1
			else:
				count[x[j]] = 1
		for ch in set(x):
			if ch in recipes:
				recipes[ch] += 1
			else:
				recipes[ch] = 1
	(num, den) = (0, 0)
	for key in recipes:
		num += math.log(recipes[key])
		den += len(a) * math.log(count[key])
	return math.exp(num - den)
t = int(input())
for _ in range(t):
	l = int(input())
	alice = []
	bob = []
	vowels = set('aeiou')
	for i in range(l):
		s = input()
		count = 2
		for j in range(len(s)):
			if s[j] in vowels:
				count += 1
			else:
				if count <= 1:
					bob.append(s)
					break
				count = 0
		else:
			alice.append(s)
	s1 = score(alice)
	s2 = score(bob)
	if s2 == 0 or math.exp(math.log(s1) - math.log(s2)) > 10 ** 7:
		print('Infinity')
	else:
		print(math.exp(math.log(s1) - math.log(s2)))


import math

def score(df):
	(res, fx, li2, x) = ({}, 1, {}, 1)
	for val in df:
		for key in val:
			if key not in res:
				res[key] = 1
			else:
				res[key] += 1
	for val in res.values():
		fx = fx * val
	for val in res:
		li2[val] = 0
		for i in df:
			if val in i:
				li2[val] += 1
	for val in li2:
		x *= li2[val]
	return [x, fx]

def prog(li, al, bo):
	for cur in li:
		(prev, f) = (-1, 0)
		for j in range(len(cur)):
			if cur[j] not in ['a', 'e', 'i', 'o', 'u']:
				if prev == -1:
					prev = j
				elif abs(prev - j) == 2 or abs(prev - j) == 1:
					f = 1
					break
				else:
					prev = j
		if f == 1:
			bo.append(cur)
		else:
			al.append(cur)
	(sca, scb) = (score(al), score(bo))
	ans1 = math.log10(sca[0]) + len(bo) * math.log10(scb[1])
	ans2 = math.log10(scb[0]) + len(al) * math.log10(sca[1])
	return ans1 - ans2
for i in range(int(input())):
	(li, x) = ([], int(input()))
	for i in range(x):
		li.append(input())
	final = prog(li, [], [])
	print('Infinity') if final > 7.0 else print(pow(10, final))


from functools import reduce
from collections import defaultdict
II = lambda : [int(x) for x in input().split()]
PROD = lambda A: reduce(lambda x, y: x * y, A)
vowels = 'aeiou'
inf = 10 ** 7

def check(r):
	if len(r) >= 2:
		if r[0] not in vowels and r[1] not in vowels:
			return False
	elif len(r) == 1:
		if r[0] not in vowels:
			return False
	for i in range(2, len(r)):
		if r[i] not in vowels:
			if r[i - 1] not in vowels or r[i - 2] not in vowels:
				return False
	return True
T = int(input())
for _ in range(T):
	fca = defaultdict(int)
	fcb = defaultdict(int)
	xca = defaultdict(int)
	xcb = defaultdict(int)
	(Ka, Kb) = (0, 0)
	L = int(input())
	for _ in range(L):
		r = input()
		if check(r):
			Ka += 1
			for c in r:
				fca[c] += 1
			for c in set(r):
				xca[c] += 1
		else:
			Kb += 1
			for c in r:
				fcb[c] += 1
			for c in set(r):
				xcb[c] += 1
	if len(xca) > 0 and len(fca) > 0:
		(xpa, fpa) = (PROD(xca.values()), PROD(fca.values()))
	else:
		(xpa, fpa) = (1, 1)
	if len(xcb) > 0 and len(fcb) > 0:
		(xpb, fpb) = (PROD(xcb.values()), PROD(fcb.values()))
	else:
		(xpb, fpb) = (1, 1)
	score = xpa / xpb
	fps = fpb / fpa
	Ks = min(Ka, Kb)
	Ka -= Ks
	Kb -= Ks
	if fps >= 1:
		while Kb > 0:
			Kb -= 1
			score *= fpb
			while score > inf and Ka > 0:
				Ka -= 1
				score /= fpa
			if score > inf:
				break
		while Ks > 0:
			Ks -= 1
			score *= fps
			while score > inf and Ka > 0:
				Ka -= 1
				score /= fpa
			if score > inf and Ka == 0:
				break
	else:
		while Kb > 0:
			Kb -= 1
			score *= fpb
			while score > inf:
				if Ka > 0:
					Ka -= 1
					score /= fpa
				elif Ks > 0:
					Ks -= 1
					score *= fps
				else:
					break
			if score > inf:
				break
		while Ks > 0 and score != 0:
			Ks -= 1
			score *= fps
	score /= fpa ** Ka
	if score > inf:
		print('Infinity')
	else:
		print(score)


from math import log

def bob(s, f2, x2):
	for c in x2.keys():
		if c in s:
			x2[c] += 1
	for C in s:
		if f2[ord(C) - 97] == 0:
			x2[C] = 1
		f2[ord(C) - 97] += 1

def alice(s, f1, x1):
	for c in f1.keys():
		if c in s:
			x1[ord(c) - 97] += 1
	for C in s:
		if C not in f1.keys():
			x1[ord(C) - 97] = 1
			f1[C] = 0
		f1[C] += 1
T = int(input())
vowels = ['a', 'e', 'i', 'o', 'u']
for _ in range(T):
	(f1, f2, x1, x2) = (dict(), [0] * 26, [0] * 26, dict())
	n = 0
	L = int(input())
	for h in range(L):
		s = str(input())
		pos = -3
		for i in range(len(s)):
			if s[i] not in vowels:
				if i - pos < 3:
					bob(s, f2, x2)
					break
				pos = i
		else:
			if len(s) == 1 and s[0] not in vowels:
				bob(s, f2, x2)
			else:
				n += 1
				alice(s, f1, x1)
	(X1, X2, F1, F2) = (1, 1, 1, 1)
	for c in f1.keys():
		X1 *= x1[ord(c) - 97]
		F1 *= f1[c]
	for c in x2.keys():
		X2 *= x2[c]
		F2 *= f2[ord(c) - 97]
	LHS = log(X1) + (L - n) * log(F2) - log(X2) - n * log(F1)
	if LHS > log(10 ** 7):
		print('Infinity')
	else:
		print('{0:.7f}'.format(X1 / X2 * (F2 ** (L - n) / F1 ** n)))


import decimal
decimal.getcontext().prec = 16
decimal.getcontext().Emin = -1000000000
decimal.getcontext().Emax = 1000000000

def vowel(x):
	return x in 'aeiou'

def is_alice(s):
	if not vowel(s[0]) and (not vowel(s[1])):
		return False
	for i in range(2, len(s)):
		if not vowel(s[i]) and (not vowel(s[i - 1]) or not vowel(s[i - 2])):
			return False
	return True

def fast_exp(x, p):
	x = decimal.Decimal(x)
	ans = decimal.Decimal(1)
	while p > 0:
		if p & 1:
			ans *= x
		x *= x
		p >>= 1
	return ans

def get_score(strings):
	k = len(strings)
	xc = [0] * 26
	fxc = [0] * 26
	for s in strings:
		f = [0] * 26
		for x in s:
			f[ord(x) - 97] += 1
		for i in range(26):
			if f[i] > 0:
				xc[i] += 1
				fxc[i] += f[i]
	(pxc, pfxc) = (1, 1)
	for i in range(26):
		if xc[i] > 0:
			pxc *= xc[i]
			pfxc *= fxc[i]
	return decimal.Decimal(pxc) / fast_exp(pfxc, k)
for _ in range(int(input())):
	(alice, bob) = ([], [])
	for _ in range(int(input())):
		inp = input()
		if is_alice(inp):
			alice.append(inp)
		else:
			bob.append(inp)
	alice_score = get_score(alice)
	bob_score = get_score(bob)
	ratio = alice_score / bob_score
	if ratio > 10000000.0:
		print('Infinity')
	else:
		print(ratio)


import math
import sys

def isVocal(c):
	if c in ['a', 'e', 'i', 'o', 'u']:
		return 1
	else:
		return -1

def f(s, dicAliceChars, dicBobChars, dicAliceWords, dicBobWords):
	le = len(s)
	belongsToAlice = True
	if le == 2:
		if not (isVocal(s[0]) == 1 or isVocal(s[1]) == 1):
			belongsToAlice = False
	else:
		for i in range(2, le):
			if isVocal(s[i]) + isVocal(s[i - 1]) + isVocal(s[i - 2]) < 0:
				belongsToAlice = False
				break
	se = set()
	for c in list(s):
		se.add(c)
	if belongsToAlice == True:
		for c in list(s):
			dicAliceChars[c] += 1
		for e in se:
			dicAliceWords[e] += 1
	else:
		for c in list(s):
			dicBobChars[c] += 1
		for e in se:
			dicBobWords[e] += 1
	if belongsToAlice == True:
		return 1
	else:
		return 0

def solveTestCase(instance):
	alphabet = list('abcdefghijklmnopqrstuvwxyz')
	dicAliceChars = {}
	dicBobChars = {}
	dicAliceWords = {}
	dicBobWords = {}
	for c in alphabet:
		dicAliceChars[c] = 0
		dicBobChars[c] = 0
		dicAliceWords[c] = 0
		dicBobWords[c] = 0
	wordsAlice = 0
	wordsBob = 0
	for str in instance:
		wordsAlice += f(str, dicAliceChars, dicBobChars, dicAliceWords, dicBobWords)
	wordsBob = len(instance) - wordsAlice
	numeratorAlice = 1
	denominatorAlice = 1
	numeratorBob = 1
	denominatorBob = 1
	res = 0
	vA = 0
	vB = 0
	for c in alphabet:
		if dicAliceChars[c] > 0:
			res += math.log(dicAliceWords[c], 10)
			vA += math.log(dicAliceChars[c], 10)
		if dicBobChars[c] > 0:
			res -= math.log(dicBobWords[c], 10)
			vB += math.log(dicBobChars[c], 10)
	res -= wordsAlice * vA
	res += wordsBob * vB
	if res >= 7:
		print('Infinity')
	else:
		print(10 ** res)
T = int(sys.stdin.readline())
for t in range(T):
	N = int(sys.stdin.readline())
	instance = []
	for n in range(N):
		s = sys.stdin.readline()
		if s[-1] == '\n':
			instance.append(s[:-1])
		else:
			instance.append(s)
	solveTestCase(instance)


vowels = ['a', 'e', 'i', 'o', 'u']

def check(s):
	n = len(s)
	if n == 2:
		if s[0] not in vowels and s[1] not in vowels:
			return False
	for i in range(1, n - 1):
		if s[i] in vowels:
			if s[i - 1] not in vowels and s[i + 1] not in vowels:
				return False
		elif s[i - 1] not in vowels or s[i + 1] not in vowels:
			return False
	return True
for _ in range(int(input())):
	n = int(input())
	s = []
	for i in range(n):
		s.append(input())
	alice = []
	bob = []
	for i in s:
		if check(i):
			alice.append(i)
		else:
			bob.append(i)
	a1 = [0] * 27
	a2 = [0] * 27
	b1 = [0] * 27
	b2 = [0] * 27
	ref = [0] * 27
	asize = len(alice)
	bsize = len(bob)
	for i in alice:
		for j in i:
			t = ord(j) - ord('a')
			a1[t] += 1
			if ref[t] == 0:
				a2[t] += 1
				ref[t] += 1
		ref = [0] * 27
	for i in bob:
		for j in i:
			t = ord(j) - ord('a')
			b1[t] += 1
			if ref[t] == 0:
				b2[t] += 1
				ref[t] += 1
		ref = [0] * 27
	numeratora = 1
	numeratorb = 1
	denominatora = 1
	denominatorb = 1
	temp = 1
	for i in range(27):
		if a2[i]:
			numeratora *= a2[i]
		if b2[i]:
			numeratorb *= b2[i]
		if a1[i]:
			denominatora *= a1[i]
		if b1[i]:
			denominatorb *= b1[i]
	if denominatorb == denominatora:
		temp = pow(denominatora, bsize - asize)
	elif asize == bsize:
		temp = pow(denominatorb / denominatora, asize)
	else:
		if bsize % 2 == 0:
			temp1 = pow(denominatorb, bsize // 2)
		else:
			temp1 = pow(denominatorb, bsize // 2 + 1)
		if asize % 2 == 0:
			temp2 = pow(denominatora, asize // 2)
		else:
			temp2 = pow(denominatora, asize // 2 + 1)
		temp = temp1 / temp2
		temp *= temp
		if bsize % 2 != 0:
			temp = temp / denominatorb
		if asize % 2 != 0:
			temp = temp * denominatora
	ans = numeratora / numeratorb * temp
	if ans > 10 ** 7:
		print('Infinity')
	else:
		print('%.10f' % ans)


import string
import math
t = int(input())
for opo in range(t):
	recipe_a = 0
	recipe_b = 0
	n = int(input())
	alice = {}
	d_alice = {}
	bob = {}
	d_bob = {}
	for w in range(0, n):
		flag_m = dict.fromkeys(string.ascii_lowercase, 0)
		S = input()
		i_con = 0
		i = 1
		flag = 0
		for j in S:
			if j == 'a' or j == 'e' or j == 'i' or (j == 'o') or (j == 'u'):
				i += 1
				continue
			else:
				if i_con == 0:
					i_con = i
				else:
					temp = i - i_con
					i_con = i
					if temp <= 2:
						flag = 1
						break
				i += 1
		if flag == 0:
			recipe_a += 1
			for j in S:
				if flag_m[j] == 0:
					if j in alice:
						alice[j] += 1
					else:
						alice[j] = 1
					flag_m[j] = 1
				if j not in d_alice:
					d_alice[j] = 1
				else:
					d_alice[j] += 1
		else:
			recipe_b += 1
			for j in S:
				if flag_m[j] == 0:
					if j in bob:
						bob[j] += 1
					else:
						bob[j] = 1
					flag_m[j] = 1
				if j not in d_bob:
					d_bob[j] = 1
				else:
					d_bob[j] += 1
	sca = 0
	scb = 0
	sca1 = 0
	scb2 = 0
	for k in alice:
		sca = sca + math.log10(alice[k])
	for k in d_alice:
		sca1 = sca1 + math.log10(d_alice[k])
	sca1 = recipe_a * sca1
	sca = sca - sca1
	for k in bob:
		scb = scb + math.log10(bob[k])
	for k in d_bob:
		scb2 = scb2 + math.log10(d_bob[k])
	scb2 = recipe_b * scb2
	scb = scb - scb2
	if sca - scb > 7:
		print('Infinity')
	else:
		print(math.pow(10, sca - scb))


import math

def check(ch):
	return ch not in 'aeiou'

def find(s):
	j = 0
	for i in range(len(s)):
		if check(s[i]):
			j = i
			break
	for i in range(i + 1, len(s)):
		if check(s[i]):
			if i - j < 3:
				return False
			j = i
	return True
for _ in range(int(input())):
	n = int(input())
	l = []
	(a, b) = ([], [])
	for __ in range(n):
		s = input()
		if find(s):
			a.append(s)
		else:
			b.append(s)
	k1 = len(a)
	k2 = len(b)
	(ra, rb) = (1, 1)
	(la, lb) = (0.0, 0.0)
	for ch in 'qwertyuiopasdfghjklzxcvbnm':
		(x, fx) = (0, 0)
		for s in a:
			if ch in s:
				x += 1
				fx += s.count(ch)
		if x > 0:
			la += math.log10(x) - k1 * math.log10(fx)
		(y, fy) = (0, 0)
		for s in b:
			if ch in s:
				y += 1
				fy += s.count(ch)
		if y > 0:
			lb += math.log10(y) - k2 * math.log10(fy)
	if la - lb > 7.0:
		print('Infinity')
	else:
		print('{0:.7f}'.format(pow(10, la - lb)))
	pass


def find_chef(recipe):
	vovels = 'aeiou'
	for i in range(len(recipe)):
		try:
			if recipe[i] not in vovels and recipe[i + 1] not in vovels:
				return 'bob'
		except IndexError:
			pass
		try:
			if recipe[i] not in vovels and recipe[i + 2] not in vovels:
				return 'bob'
		except IndexError:
			pass
	return 'alice'

def update_alice_dict(alice_dict, recipe):
	visited = ''
	for letter in recipe:
		alice_dict[letter][1] += 1
		if letter not in visited:
			alice_dict[letter][0] += 1
			visited += letter
	return alice_dict

def update_bob_dict(bob_dict, recipe):
	visited = ''
	for letter in recipe:
		bob_dict[letter][1] += 1
		if letter not in visited:
			bob_dict[letter][0] += 1
			visited += letter
	return bob_dict
for case in range(int(input())):
	n_alice = 0
	n_bob = 0
	alice_dict = {'a': [0, 0], 'b': [0, 0], 'c': [0, 0], 'd': [0, 0], 'e': [0, 0], 'f': [0, 0], 'g': [0, 0], 'h': [0, 0], 'i': [0, 0], 'j': [0, 0], 'k': [0, 0], 'l': [0, 0], 'm': [0, 0], 'n': [0, 0], 'o': [0, 0], 'p': [0, 0], 'q': [0, 0], 'r': [0, 0], 's': [0, 0], 't': [0, 0], 'u': [0, 0], 'v': [0, 0], 'w': [0, 0], 'x': [0, 0], 'y': [0, 0], 'z': [0, 0]}
	bob_dict = {'a': [0, 0], 'b': [0, 0], 'c': [0, 0], 'd': [0, 0], 'e': [0, 0], 'f': [0, 0], 'g': [0, 0], 'h': [0, 0], 'i': [0, 0], 'j': [0, 0], 'k': [0, 0], 'l': [0, 0], 'm': [0, 0], 'n': [0, 0], 'o': [0, 0], 'p': [0, 0], 'q': [0, 0], 'r': [0, 0], 's': [0, 0], 't': [0, 0], 'u': [0, 0], 'v': [0, 0], 'w': [0, 0], 'x': [0, 0], 'y': [0, 0], 'z': [0, 0]}
	no_of_strings = int(input())
	for p in range(no_of_strings):
		recipe = input()
		chef = find_chef(recipe)
		if chef == 'bob':
			n_bob += 1
			bob_dict = update_bob_dict(bob_dict, recipe)
		else:
			n_alice += 1
			alice_dict = update_alice_dict(alice_dict, recipe)
	if no_of_strings <= 10:
		score_alice = 1
		score_bob = 1
		for letter in alice_dict.keys():
			if alice_dict[letter][0] > 0:
				num = alice_dict[letter][0]
				dem = alice_dict[letter][1] ** n_alice
				score_alice *= num / dem
			if bob_dict[letter][0] > 0:
				num = bob_dict[letter][0]
				dem = bob_dict[letter][1] ** n_bob
				score_bob *= num / dem
		score = score_alice / score_bob
		if score > 10000000:
			print('Infinity')
		else:
			print(score)
	else:
		nums = []
		dens = []
		for letter in alice_dict.keys():
			if alice_dict[letter][0] > 0:
				num = alice_dict[letter][0]
				dem = alice_dict[letter][1]
				nums.append(num)
				for q in range(n_alice):
					dens.append(dem)
			if bob_dict[letter][0] > 0:
				num = bob_dict[letter][0]
				dem = bob_dict[letter][1]
				for q in range(n_bob):
					nums.append(dem)
				dens.append(num)
		l_n = len(nums)
		l_d = len(dens)
		i = j = 0
		score = 1
		infinity_flag = False
		zero_flag = False
		while i < l_n or j < l_d:
			if j >= l_d and i < l_n:
				score *= nums[i]
				i += 1
				if score > 10000000.0 - 10:
					infinity_flag = True
					break
			elif i == l_n and j < l_d:
				score /= dens[j]
				j += 1
				if score < 1e-09:
					zero_flag = True
					break
			elif score > 10000000.0:
				score /= dens[j]
				j += 1
			else:
				score *= nums[i]
				i += 1
		if infinity_flag:
			print('Infinity')
		else:
			print(score)


from math import log10

def sub(nums, k):
	(count, p, d) = (0, 0, {0: 1})
	(vowel, cons) = (0, 0)
	check = {'a': 0, 'e': 0, 'i': 0, 'o': 0, 'u': 0}
	d1 = {}
	for i in nums:
		if i in check:
			x = -1
			vowel += 1
		else:
			x = 1
			cons += 1
		p += x
		if p - k in d:
			count += d[p - k]
		if p not in d:
			d[p] = 1
		else:
			d[p] += 1
		if i not in d1:
			d1[i] = 1
		else:
			d1[i] += 1
	return (count, d1, vowel, cons)
s = 'abcdefghijklmnopqrstuvwxyz'
d = {}
for i in range(26):
	d[s[i]] = i
te = int(input())
finallfy = []
for _ in range(te):
	n = int(input())
	hy = 0
	pura = []
	(alice_up, alice_count, bob_up, bob_count) = ([0] * 26, [0] * 26, [0] * 26, [0] * 26)
	for _ in range(n):
		s = input()
		pura.append(s)
	for i in range(n):
		(ans, d1, vowel, conso) = sub(pura[i], 1)
		if conso == 0 or (ans <= conso and vowel != 0):
			hy += 1
			for (x, y) in d1.items():
				alice_up[d[x]] += 1
				alice_count[d[x]] += y
		else:
			for (x, y) in d1.items():
				bob_up[d[x]] += 1
				bob_count[d[x]] += y
	(ans_alice, ans_al, ans_bob, ans_b) = (1, 1, 1, 1)
	for i in range(26):
		if alice_up[i] != 0:
			ans_alice *= alice_up[i]
			ans_al *= alice_count[i]
		if bob_up[i] != 0:
			ans_bob *= bob_up[i]
			ans_b *= bob_count[i]
	ert = log10(ans_alice / ans_bob) + ((n - hy) * log10(ans_b) - hy * log10(ans_al))
	if ert > 7:
		finallfy.append('Infinity')
	else:
		finallfy.append(10 ** ert)
for x in finallfy:
	print(x)


from collections import defaultdict
import math

def substring(s):
	prev = -1
	for i in range(len(s)):
		if s[i] not in ['a', 'e', 'i', 'o', 'u']:
			if prev == -1:
				prev = i
			elif abs(prev - i) == 1 or abs(prev - i) == 2:
				return 0
			else:
				prev = i
	return 1
for _ in range(int(input())):
	l = int(input())
	alice = []
	bob = []
	m_a = defaultdict(lambda : 0)
	m_b = defaultdict(lambda : 0)
	res_a = defaultdict(lambda : 0)
	res_b = defaultdict(lambda : 0)
	for i in range(l):
		s = input()
		if substring(s):
			alice.append(s)
		else:
			bob.append(s)
	s_alice = len(alice)
	s_bob = len(bob)
	for i in alice:
		for j in i:
			m_a[j] += 1
	for i in m_a:
		for j in alice:
			if i in j:
				res_a[i] += 1
	for i in bob:
		for j in i:
			m_b[j] += 1
	for i in m_b:
		for j in bob:
			if i in j:
				res_b[i] += 1
	num_alice = 1
	num_bob = 1
	d_alice = 1
	d_bob = 1
	for i in m_a:
		num_alice *= res_a[i]
		d_alice *= m_a[i]
	for i in m_b:
		num_bob *= res_b[i]
		d_bob *= m_b[i]
	if l <= 10:
		if s_bob >= s_alice:
			k1 = math.pow(d_bob / d_alice, s_alice) * math.pow(d_bob, s_bob - s_alice)
		else:
			k1 = math.pow(d_bob / d_alice, s_bob) * math.pow(d_alice, -(s_alice - s_bob))
		ans = num_alice / num_bob
		ans = ans * k1
		if ans > 10000000:
			print('Infinity')
		else:
			print(ans)
	else:
		ALICE = math.log10(num_alice) + s_bob * math.log10(d_bob)
		BOB = math.log10(num_bob) + s_alice * math.log10(d_alice)
		ans = ALICE - BOB
		if ans > 7.0:
			print('Infinity')
		else:
			ans = pow(10, ans)
			print(ans)