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≤$N$≤104
2≤|$s_i$|≤10
$s_i$ consists of uppercase English letters.
Input
Input is given from Standard Input in the following format:
1 2 3 4
N s1 \dots s_N
Output
Print the answer.
Sample Input 1
1 2 3 4
3 ABCA XBAZ BAD
Sample Output 1
1
2
For example, if we concatenate ABCA, BAD and XBAZ in this order, the resulting string ABCABADXBAZ has two occurrences of AB.
Sample Input 2
1 2 3 4 5 6 7 8 9 10
9 BEWPVCRWH ZZNQYIJX BAVREA PA HJMYITEOX BCJHMRMNK BP QVFABZ PRGKSPUNA
Sample Output 2
1
4
Sample Input 3
1 2 3 4 5 6 7 8
7 RABYBBE JOZ BMHQUVA BPA ISU MCMABAOBHZ SZMEHMA
Sample Output 3
1
4
Analysis
This is to find how many strings that starts with A and ends with B and the number of AB inside the string. Since strings start with A and end with B has coincidence, so the number of AB that comes from concatenation is min(number of strings start with A, number of string end with B).
Note: If all the strings that satisfy the above statement and satisfy both (start with A and start with B) , the answer should be -1 because if strings are BA and BA, it can only be concatenated to BABA, which has only one AB.