Devu is a disastrous oracle: his predictions about various events of your life are horrifying. Instead of providing good luck, he "blesses" you with bad luck. The secret behind his wickedness is a hidden omen which is a string of length m. On your visit to him, you can ask a lot of questions about your future, each of which should be a string of length m. In total you asked him n such questions, denoted by strings s1, s2, ... , sn of length m each. Each of the question strings is composed of the characters 'a' and 'b' only.

Amount of bad luck this visit will bring you is equal to the length of longest common subsequence (LCS) of all the question strings and the hidden omen string. Of course, as the omen string is hidden, you are wondering what could be the least value of bad luck you can get.

Can you find out what could be the least bad luck you can get? Find it fast, before Devu tells you any bad omens.

-----Input-----
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
First line of each test case contains a single integer n denoting number of strings.
For each of next n lines, the ith line contains the string si.

-----Output-----
For each test case, output a single integer corresponding to the answer of the problem. 


-----Constraints-----
- All the strings (including the hidden omen) contain the characters 'a' and 'b' only.

Subtask #1: (40 points) 

- 1 ≤ T, n, m ≤ 14

Subtask #2: (60 points) 

- 1 ≤ T, n, m ≤ 100

-----Example-----
Input:3
2
ab
ba
2
aa
bb
3
aabb
abab
baab

Output:1
0
2

-----Explanation-----
In the first example, the minimum value of LCS of all the strings is 1, the string by oracle can be one of these {aa, ab, ba, bb}. 

In the second example, whatever string oracle has does not matter, LCS will always be zero.

Difficulty: interview

Starter code:

Solutions:
t = int(input())
for j in range(0, t):
 n = int(input())
 m = 100
 for i in range(0, n):
  str = input()
  p = min(str.count("a",0,len(str)),str.count("b",0,len(str)))
  if (m > p):
   m = p
 print(m)
 t = t-1

for i in range(int(input())):
  n=int(input())
  li_a=li_b=[]
  for i in range(n):
    s=input()
    li_a.append(s.count('a'))
    li_b.append(s.count('b'))
  print(min(min(li_a),min(li_b)))


# your code goes here

t = int(input())
while (t>0):
 t = t-1
 n = int(input())
 a = 100000000
 b = 100000000
 for i in range (0,n):
  s = str(input())
  l = s.count('a')
  if (l < a):
   a = l
  l = s.count('b')
  if (l < b):
   b = l
 print(min(a, b))

# cook your code here
t=int(input())
for unused in range(t):
 n=int(input())
 minA=200
 minB=200
 for used in range(n):
  inputString=input()
  countA=0
  countB=0
  for i in inputString:
   if i=='a':
    countA+=1
   else:
    countB+=1
  if countA<minA:
   minA=countA
  if countB<minB:
   minB=countB
 print(min(minA,minB))
 
 
 

  
  


t = eval(input())
for i in range(t):
 n = eval(input())
 d = {'a':1000,'b':1000}
 for j in range(n):
  str = input()
  d['a']= min(str.count('a'),d['a'])
  d['b']= min(str.count('b'),d['b'])
 print(min(d['a'],d['b'])) 

# cook your code here
T = int(input())
for _ in range(T):
 N = int(input())
 A = [0]*N
 for i in range(N):
  s = input()
  ca = 0
  cb = 0
  for x in s:
   if x == 'a':
    ca += 1
   else:
    cb += 1
  A[i] = min(ca,cb)
 print(min(A))


import sys

t = int(input())

while t > 0:
 n = int(input())
 minimum = sys.maxsize
 while n > 0:
  s = input()
  minimum = min(minimum, s.count('a'), s.count('b'))
  n = n - 1
 print(minimum)
 t = t - 1

import sys

T = int(input())

result = ""

def getMin(matrix, N, M):
 smallest = sys.maxsize
 for i in range(0, N):
  for j in range(0, M):
   if matrix[i][j] < smallest:
    smallest = matrix[i][j]
 return smallest

for i in range(0, T):
 N = int(input())
 matrix = [[0 for x in range(2)] for x in range(N)]
 for j in range(0, N):
  text = input()
  for c in text:
   if(c == "a"):
    matrix[j][0] += 1
   else:
    matrix[j][1] += 1
 result += str(getMin(matrix, N, 2)) + "\n"

print(result)

def f(n):
 s=list(input().strip())
 mina=len([x for x in s if x=='a'])
 ln=len(s)
 minb=ln-mina
 for i in range(n-1):
  s=list(input().strip())
  curra=len([x for x in s if x=='a'])
  currb=len([x for x in s if x=='b'])
  if mina>curra:
   mina=curra
  if minb>currb:
   minb=currb
 return min(mina,minb)
t=int(input())
for i in range(t):
 n=int(input())
 print(f(n)) 

for _ in range(int(input())):
 lst=[]
 for nn in range(int(input())):
  stg=input()
  chck=list(set(stg))
  if chck==['a'] or chck==['b']:
   lst.append(0)
   continue
  else:
   lst.append(min(stg.count('a'),stg.count('b')))
 print(min(lst))
   


def lcs(A,B):
 a,b=len(A),len(B)
 lst=[[None]*(b+1) for _ in range(a+1)]
 for x in range(a+1):
  for y in range(b+1):
   if x==0 or y==0:
    lst[x][y]=0
   elif A[x-1] == B[y-1]:
    lst[x][y]= 1+lst[x-1][y-1]
   else:
    lst[x][y]=max(lst[x][y-1],lst[x-1][y])
 return lst[a][b]

for _ in range(int(input())):
 n=int(input())
 lst=[]
 for i in range(n):
  stg=input()
  axx=list(set(stg))
  if axx == ['a'] or axx == ['b']:
   lst.append(0)
   continue
  m=len(stg)
  cnta=stg.count('a')
  cntb=stg.count('b')
  if cnta>cntb:
   lst.append(lcs(stg,m*'b'))
  else:
   lst.append(lcs(stg,m*'a'))
 print(min(lst))


t=eval(input())
while t:
 m=101
 n=eval(input())
 while n:
  s=input()
  a=s.count('a')
  b=s.count('b')
  m=min(a, b, m)
  n-=1
 print(m)
 t-=1

def lcs(A,B):
 a,b=len(A),len(B)
 lst=[[None]*(b+1) for _ in range(a+1)]
 for x in range(a+1):
  for y in range(b+1):
   if x==0 or y==0:
    lst[x][y]=0
   elif A[x-1] == B[y-1]:
    lst[x][y]= 1+lst[x-1][y-1]
   else:
    lst[x][y]=max(lst[x][y-1],lst[x-1][y])
 return lst[a][b]

for _ in range(int(input())):
 n=int(input())
 lst=[]
 for i in range(n):
  stg=input()
  axx=list(set(stg))
  if axx == ['a'] or axx == ['b']:
   lst.append(0)
   continue
  m=len(stg)
  cnta=stg.count('a')
  cntb=stg.count('b')
  if cnta>cntb:
   lst.append(lcs(stg,m*'b'))
  elif cntb>cnta:
   lst.append(lcs(stg,m*'a'))
  else:
   lst.append(min(lcs(stg,m*'a'),lcs(stg,m*'b')))
 print(min(lst))


def lcs(A,B):
 a,b=len(A),len(B)
 lst=[[None]*(b+1) for _ in range(a+1)]
 for x in range(a+1):
  for y in range(b+1):
   if x==0 or y==0:
    lst[x][y]=0
   elif A[x-1] == B[y-1]:
    lst[x][y]= 1+lst[x-1][y-1]
   else:
    lst[x][y]=max(lst[x][y-1],lst[x-1][y])
 return lst[a][b]

for _ in range(int(input())):
 n=int(input())
 lst=[]
 for i in range(n):
  stg=input()
  m=len(stg)
  cnta=stg.count('a')
  cntb=stg.count('b')
  if cnta>cntb:
   lst.append(lcs(stg,m*'b'))
  elif cntb>cnta:
   lst.append(lcs(stg,m*'a'))
  else:
   lst.append(min(lcs(stg,m*'a'),lcs(stg,m*'b')))
 print(min(lst))


def lcs(A,B):
 a,b=len(A),len(B)
 lst=[[0]*(b+1) for _ in range(a+1)]
 for x in range(1,a+1):
  for y in range(1,b+1):
   if A[x-1] == B[y-1]:
    lst[x][y]= 1+lst[x-1][y-1]
   else:
    lst[x][y]=max(lst[x][y-1],lst[x-1][y])
 return lst[a][b]

for _ in range(int(input())):
 n=int(input())
 lst=[]
 for i in range(n):
  stg=input()
  m=len(stg)
  lst.append(min(lcs(stg,m*'a'),lcs(stg,m*'b')))
 print(min(lst))


t=eval(input())
for qq in range(t):
 n=eval(input())
 s=input()
 amin=0
 bmin=0
 for x in s:
  if x =="a":amin+=1
  else:bmin+=1
 #print s,amin,bmin
 for cc in range(n-1):
  s=input()
  ca=0
  cb=0
  for x in s:
   if x=="a":ca+=1
   else:cb+=1
  amin=min(ca,amin)
  bmin=min(cb,bmin)
 #   print s,amin,bmin
 print(min(amin,bmin))

t = int(input())
for i in range(t):
 n = int(input())
 min_a = 1000
 min_b = 1000
 for j in range(n):
  tmp_a = 0
  tmp_b = 0
  str1 = input()
  for e in str1:
   if(e == 'a'):
    tmp_a+=1
   elif(e == 'b'):
    tmp_b+=1
  min_a = min(min_a, tmp_a)
  min_b = min(min_b, tmp_b)
 print(min(min_b, min_a))


t = int(input())
for i in range(t):
 n = int(input())
 min_a = 1000
 min_b = 1000
 for j in range(n):
  tmp_a = 0
  tmp_b = 0
  str1 = input()
  for e in str1:
   if(e == 'a'):
    tmp_a+=1
   elif(e == 'b'):
    tmp_b+=1
  min_a = min(min_a, tmp_a)
  min_b = min(min_b, tmp_b)
 print(min(min_b, min_a))


for x in range(0,int(input())):
 k,q=int(input()),100000
 for y in range(0,k):
  s=input()
  q=min(min(s.count('a'),s.count('b')),q)
 print(q)

for x in range(0,int(input())):
 k=int(input())
 ctra,ctrb=[None]*k,[None]*k
 for y in range(0,k):
  s=input()
  ctra[y],ctrb[y]=s.count('a'),s.count('b')
 print(min(min(ctra),min(ctrb)))