问题描述

Snuke有 $N$ 个字符串，第 $i$ 个字符串为 $s_i$。

将这些字符串按照某种顺序连接成一个字符串。找出结果字符串中 AB 的最大可能出现次数。

约束条件

• $1 \\leq N \\leq 10^{4}$
• $2 \\leq |s_i| \\leq 10$
• $s_i$ 由大写英文字母组成。

输入

输入从标准输入读取，格式如下：

$N$

$s_1$

$\\vdots$

$s_N$

输出

打印答案。

示例输入 1

3
ABCA
XBAZ
BAD

示例输出 1

2

例如，如果我们按照顺序连接 ABCA、BAD 和 XBAZ，得到的字符串 ABCABADXBAZ 中有两个 AB。

示例输入 2

9
BEWPVCRWH
ZZNQYIJX
BAVREA
PA
HJMYITEOX
BCJHMRMNK
BP
QVFABZ
PRGKSPUNA

示例输出 2

4

示例输入 3

7
RABYBBE
JOZ
BMHQUVA
BPA
ISU
MCMABAOBHZ
SZMEHMA

示例输出 3

4