Snuke has N strings. The i-th string is s_i.

Let us concatenate these strings into one string after arranging them in some order. Find the maximum possible number of occurrences of `AB` in the resulting string.

Constraints

* 1 \leq N \leq 10^{4}
* 2 \leq |s_i| \leq 10
* s_i consists of uppercase English letters.

Input

Input is given from Standard Input in the following format:


N
s_1
\vdots
s_N


Output

Print the answer.

Examples

Input

3
ABCA
XBAZ
BAD


Output

2


Input

9
BEWPVCRWH
ZZNQYIJX
BAVREA
PA
HJMYITEOX
BCJHMRMNK
BP
QVFABZ
PRGKSPUNA


Output

4


Input

7
RABYBBE
JOZ
BMHQUVA
BPA
ISU
MCMABAOBHZ
SZMEHMA


Output

4
import collections
c = 0
cc = collections.Counter()
for _ in range(int(raw_input())):
	w = raw_input()
	for u in range(len(w)-1):
		if w[u:u+2] == 'AB': c+=1
	w = w.replace('AB','')
	if len(w) == 1:
		s = (w[0] if w[0] == 'A' or w[0] == 'B' else '')
	if len(w) >= 2:
		s = (w[0] if w[0] == 'A' or w[0] == 'B' else '') + (w[-1] if w[-1] == 'A' or w[-1] == 'B' else '')
	
	if s: cc[s]+=1
q= 0 #max(0,cc['BA'] - 1)
if cc['BA']:
	q += cc['BA'] -1
	if cc['A']:
		cc['A']-=1
		q+=1 
	if cc['B']:
		cc['B']-=1
		q+=1 
print c + q + min(cc['A']+cc['AA'],cc['B']+cc['BB'])
"""
A
AA
B
BB
AB
BA

 A - [BA - BA - BA - BA - BA - BA]  - B 
 A - B 



    [AB - AB - AB - AB - AB - AB ]

    A - B - A  - B  

"""