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$
# cook your dish here
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
   else:
    if consonant_index==-1:
     consonant_index=j
    else:
     if 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'))
  denom_a=decimal.Decimal(1).quantize(decimal.Decimal('0.0000000001'))
  denom_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=100


  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))
# cook your dish here
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
   else:
    if consonant_index==-1:
     consonant_index=j
    else:
     if 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'))
  denom_a=decimal.Decimal(1).quantize(decimal.Decimal('0.0000000001'))
  denom_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=100


  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))