Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 

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 s_{1}, s_{2}, ... , s_{n} 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 i^{th} line contains the string s_{i}.

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

----- Sample Input 1 ------ 
3
2
ab
ba
2
aa
bb
3
aabb
abab
baab
----- Sample Output 1 ------ 
1
0
2
----- explanation 1 ------ 
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: MEDIUM_HARD

Starter code:

Solutions:
t = int(input())
for i in range(t):
	n = int(input())
	a = 100
	b = 100
	for j in range(n):
		s = input()
		a = min(a, s.count('a'))
		b = min(b, s.count('b'))
	print(min(a, b))


for _ in range(int(input())):
	a = b = 100
	for _ in range(int(input())):
		s = input()
		a = min(a, s.count('a'))
		b = min(b, s.count('b'))
	print(min(a, b))


for _ in range(int(input())):
	l = int(input())
	ac = 101
	bc = 101
	for i in range(l):
		ques = input()
		ac = min(ques.count('a'), ac)
		bc = min(ques.count('b'), bc)
		res = min(ac, bc)
	print(res)


T = int(input())
for t in range(T):
	n = int(input())
	(x, y) = (100, 100)
	for i in range(n):
		s = str(input())
		a = s.count('a')
		if a < x:
			x = a
		b = s.count('b')
		if b < y:
			y = b
	print(min(x, y))


for _ in range(int(input())):
	n = int(input())
	counta = 101
	countb = 101
	for i in range(n):
		text = input()
		counta = min(text.count('a'), counta)
		countb = min(text.count('b'), countb)
	print(min(counta, countb))


def getCount(A):
	(a, b) = (0, 0)
	for i in A:
		if i == 'a':
			a += 1
		else:
			b += 1
	return (a, b)
T = int(input())
ans = []
for _ in range(T):
	N = int(input())
	S = []
	for i in range(N):
		x = input()
		S.append(x)
	(a, b) = getCount(S[0])
	for i in range(1, N):
		(ai, bi) = getCount(S[i])
		a = min(a, ai)
		b = min(b, bi)
	ans.append(min(a, b))
for i in ans:
	print(i)


t = int(input())
for _ in range(t):
	n = int(input())
	(a, b) = (101, 101)
	for i in range(n):
		arr = input()
		a_temp = arr.count('a')
		if a_temp < a:
			a = a_temp
		b_temp = arr.count('b')
		if b_temp < b:
			b = b_temp
	print(min(a, b))


t = int(input())
while t:
	n = int(input())
	(ma, mb) = (float('inf'), float('inf'))
	for i in range(n):
		s = input()
		ma = min(ma, s.count('a'))
		mb = min(mb, s.count('b'))
	print(int(min(ma, mb)))
	t -= 1


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


t = int(input())
for _ in range(t):
	mat = []
	n = int(input())
	na = 1000000000.0
	nb = 1000000000.0
	for _ in range(n):
		s = input()
		na = min(na, s.count('a'))
		nb = min(nb, s.count('b'))
	print(min(na, nb))


T = int(input())
for i in range(T):
	c = int(input())
	l = []
	for i in range(c):
		y = input()
		a = min(y.count('a'), 9999999999)
		b = min(y.count('b'), 9999999999)
		e = min(a, b)
		l.append(e)
	print(min(l))


for _ in range(int(input())):
	A = B = 10 ** 9
	for _ in range(int(input())):
		s = input()
		A = min(A, sum((c == 'a' for c in s)))
		B = min(B, sum((c == 'b' for c in s)))
	print(min(A, B))


for case in range(int(input())):
	A = 10 ** 9
	B = 10 ** 9
	for i in range(int(input())):
		s = input()
		A = min(A, sum((c == 'a' for c in s)))
		B = min(B, sum((c == 'b' for c in s)))
	print(min(A, B))


t = input()

def balloon(t):
	for i in range(int(t)):
		stri = int(input())
		l = []
		for a in range(stri):
			set = input()
			a = 999999999999999999
			b = 999999999999999999
			a = min(set.count('a'), a)
			b = min(set.count('b'), b)
			l.append(min(a, b))
		print(min(l))
balloon(t)


for _ in range(int(input())):
	n = int(input())
	l = []
	a = b = 10 ** 9
	for i in range(n):
		l.append(input())
	for i in l:
		a = min(a, sum([c == 'a' for c in i]))
		b = min(b, sum([c == 'b' for c in i]))
	print(min(a, b))


for _ in range(int(input())):
	n = int(input())
	minia = 100000000000
	minib = 1000000000000
	for i in range(n):
		s = input()
		minia = min(minia, s.count('a'))
		minib = min(minib, s.count('b'))
	print(min(minia, minib))


for _ in range(int(input())):
	n = int(input())
	ma = 1000000000
	mb = 1000000000
	for i in range(n):
		text = input()
		ma = min(text.count('a'), ma)
		mb = min(text.count('b'), mb)
	print(min(ma, mb))


for t in range(int(input())):
	n = int(input())
	na = nb = 100
	for i in range(n):
		q = input()
		na = min(na, q.count('a'))
		nb = min(nb, q.count('b'))
	print(min(na, nb))


T = int(input())
for t in range(T):
	n = int(input())
	res = 200
	for i in range(n):
		a = input()
		res = min(res, a.count('a'), a.count('b'))
	print(res)


for _ in range(int(input())):
	output_int = 99999999999
	for _ in range(int(input())):
		input_str = input()
		a_count = min(output_int, input_str.count('a'))
		b_count = min(output_int, input_str.count('b'))
		output_int = min(a_count, b_count)
	print(output_int)


test_cases = int(input())
count = 0
while count < test_cases:
	i = int(input())
	(jj, count1) = (0, 999999999999999)
	while jj < i:
		str = input()
		length = len(str)
		k = count2 = count3 = 0
		while k < length:
			if str[k] == 'a':
				count2 = count2 + 1
			else:
				count3 = count3 + 1
			k = k + 1
		count1 = min(count1, count2, count3)
		jj = jj + 1
	count = count + 1
	print(count1)


from sys import stdin
import sys
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	A = B = float('inf')
	for _ in range(n):
		s = stdin.readline()
		A = min(A, sum((c == 'a' for c in s)))
		B = min(B, sum((c == 'b' for c in s)))
	print(min(A, B))


for i in range(int(input())):
	n = int(input())
	mn = 1004
	for i in range(n):
		s = input()
		mn = min(mn, min((s.count(x) for x in ('a', 'b'))))
	print(mn)


l = ['a', 'b']
for i in range(int(input())):
	n = int(input())
	mn = 105
	for i in range(n):
		s = input()
		for x in l:
			mn = min(mn, s.count(x))
	print(mn)


test = int(input())
while test != 0:
	test -= 1
	n = int(input())
	i = 0
	ans = 100000
	while i < n:
		i += 1
		x = input()
		j = 0
		a = 0
		b = 0
		while j < len(x):
			if x[j] == 'a':
				a += 1
			else:
				b += 1
			j += 1
		ans = min(ans, a, b)
	print(ans)


t = int(input())
while t > 0:
	a = 0
	b = 0
	maxa = 1110
	maxb = 1110
	n = int(input())
	for i in range(n):
		a = 0
		b = 0
		s1 = input()
		for x in s1:
			if x == 'a':
				a = a + 1
			else:
				b = b + 1
		maxa = min(maxa, a)
		maxb = min(maxb, b)
	print(min(maxa, maxb))
	t = t - 1


t = int(input())
for i in range(t):
	mna = 101
	mnb = 101
	n = int(input())
	for k in range(n):
		s = str(input())
		a = 0
		b = 0
		for j in s:
			if j == 'a':
				a += 1
			else:
				b += 1
		mna = min(mna, a)
		mnb = min(mnb, b)
	print(min(mna, mnb))


for t in range(int(input())):
	v = 50
	for i in range(int(input())):
		s = input()
		v = min(v, s.count('a'), s.count('b'))
	print(v)


for _ in range(int(input())):
	N = int(input())
	a = []
	b = []
	for i in range(N):
		s = input()
		a.append(s.count('a'))
		b.append(s.count('b'))
	print(min(a + b))


def cnt(text):
	l = len(text)
	cnt1 = 0
	cnt2 = 0
	for i in text:
		if i == 'a':
			cnt1 += 1
		else:
			cnt2 += 1
	return min(cnt1, cnt2)
tc = 0
n = 0
tc = int(input())
while tc > 0:
	mini = 0
	n = int(input())
	txt = input()
	mini = cnt(txt)
	for i in range(1, n):
		txt = input()
		temp = cnt(txt)
		if temp <= mini:
			mini = temp
	print(mini)
	tc -= 1


t = int(input())
for i in range(1, t + 1):
	n = int(input())
	mina = -1
	minb = -1
	for j in range(1, n + 1):
		string = input()
		a = string.count('a')
		b = len(string) - a
		if mina == -1 or mina > a:
			mina = a
		if minb == -1 or minb > b:
			minb = b
	print(min(mina, minb))


k = input()
t = int(k)
while t > 0:
	n = int(input())
	mina = 105
	minb = 105
	for _ in range(0, n):
		s = input()
		a = s.count('a')
		b = len(s) - a
		mina = min(mina, a)
		minb = min(minb, b)
	if mina < minb:
		mi = mina
	else:
		mi = minb
	print(mi)
	t = t - 1


import sys
casos = int(input())
for i in range(casos):
	n = int(input())
	min_a = 1000000
	min_b = 1000000
	for j in range(n):
		line = input()
		(ca, cb) = (0, 0)
		for c in line:
			if c == 'a':
				ca += 1
			else:
				cb += 1
		min_a = min(min_a, ca)
		min_b = min(min_b, cb)
	print(min(min_a, min_b))


t = int(input())
for i in range(t):
	n = int(input())
	str_list = []
	for j in range(n):
		q_str = str(input())
		str_list.append(q_str)
	m = len(str_list[0])
	min_lcs = 101
	for j in range(n):
		a_c = str_list[j].count('a')
		b_c = str_list[j].count('b')
		min_lcs = min(a_c, b_c, min_lcs)
	print(min_lcs)


t = int(input())
for _ in range(0, t):
	n = int(input())
	mina = 101
	minb = 101
	for _ in range(0, n):
		s = input()
		a = s.count('a')
		b = s.count('b')
		if a < mina:
			mina = a
		if b < minb:
			minb = b
	print(min(mina, minb))


for t in range(int(input())):
	n = int(input())
	temp = input()
	large = min(temp.count('a'), temp.count('b'))
	for i in range(n - 1):
		temp = input()
		a = min(temp.count('a'), temp.count('b'))
		if a < large:
			large = a
	print(large)


from collections import defaultdict
t = int(input())
for x in range(0, t):
	rdic = defaultdict(list)
	rdic = {'A': [], 'B': []}
	N = int(input())
	for y in range(0, N):
		msg = input()
		count_A = 0
		for c in msg:
			if c == 'a':
				count_A += 1
		count_B = len(msg) - count_A
		rdic['A'].append(count_A)
		rdic['B'].append(count_B)
	print(min(min(rdic['A']), min(rdic['B'])))


for t in [0] * int(input()):
	A = B = 1000000000.0
	for i in [0] * int(input()):
		s = input()
		A = min(A, sum((c == 'a' for c in s)))
		B = min(B, sum((c == 'b' for c in s)))
	print(min(A, B))


T = int(input())
for i in range(T):
	n = int(input())
	c = 101
	for j in range(n):
		s = input()
		(a, b) = [0, 0]
		for k in range(len(s)):
			if s[k] == 'a':
				a += 1
			else:
				b += 1
		temp = min(a, b)
		if temp < c:
			c = temp
	print(c)


for i in range(int(input())):
	mina = 1000
	minb = 1000
	for j in range(int(input())):
		k = input()
		mina = min(mina, k.count('a'))
		minb = min(minb, k.count('b'))
	print(min(mina, minb))


for tests in range(int(input())):
	maxa = maxb = float('inf')
	for strings in range(int(input())):
		s = input()
		cura = 0
		curb = 0
		for i in s:
			if i == 'a':
				cura += 1
			else:
				curb += 1
		maxa = min(maxa, cura)
		maxb = min(maxb, curb)
	print(min(maxa, maxb))


def main():
	mode = 'filee'
	if mode == 'file':
		f = open('test.txt', 'r')
	get = lambda : [int(x) for x in (f.readline() if mode == 'file' else input()).split()]
	gets = lambda : f.readline() if mode == 'file' else input()
	[t] = get()
	for z in range(t):
		[n] = get()
		minn = 101
		for j in range(n):
			g = gets()
			g = list(g)
			minn = min(minn, g.count('a'), g.count('b'))
		print(minn)
	if mode == 'file':
		f.close()
main()


for _ in range(0, int(input())):
	m = int(input())
	s = 100
	for i in range(0, m):
		x = str(input())
		ca = x.count('a')
		cb = x.count('b')
		s = min(ca, cb, s)
	print(s)