题目描述

给定 $N$ 个只包含字符 A 和 B 的字符串。对于一个字符串 $s$，记其长度为 $|s|$，下标从 $1$ 开始编号。 我们称字符串 $s$ 是一个 好字符串，当且仅当存在若干个二元组 $(l_i,r_i)$，满足以下条件： $1 \le l_i < r_i \le |s|$； $s_{l_i}=s_{r_i}$； 每个位置 $1,2,\ldots,|s|$ 恰好出现在一个二元组中； 任意两个不同的二元组 $(l_i,r_i)$ 和 $(l_j,r_j)$，不存在如下交叉情况：

$$l_i < l_j < r_i < r_j$$

也就是说，需要将字符串中的每个字符与另一个相同字符配对，并且如果把每一对位置在字符串上方用弧线连接起来，所有弧线不能相交。 请你统计给定的 $N$ 个字符串中，有多少个是好字符串。 输入格式 第一行输入一个正整数 $N$，表示字符串个数。 接下来 $N$ 行，每行输入一个只包含字符 A 和 B 的字符串。

输出格式

输出一行一个整数，表示好字符串的数量。

输入输出样例 #1

输入 #1

3
ABAB
AABB
ABBA

输出 #1

2

输入输出样例 #2

输入 #2

3
AAA
AA
AB

输出 #2

1

输入输出样例 #3

输入 #3

1
ABBABB

输出 #3

1

样例解释

样例 #1 解释

输入的三个字符串分别为 ABAB、AABB、ABBA。

1. ABAB 字符串 ABAB 中，第 $1$ 个字符和第 $3$ 个字符都是 A，第 $2$ 个字符和第 $4$ 个字符都是 B。 只能按如下方式配对： 第 $1$ 个字符 A 和第 $3$ 个字符 A 配对； 第 $2$ 个字符 B 和第 $4$ 个字符 B 配对。 画出弧线后如下：

位置： 1   2   3   4
字符： A   B   A   B

       ┌───────┐
       │       │
       A   B   A   B
           │       │
           └───────┘

这两条弧线发生交叉，也就是出现了：

$$1 < 2 < 3 < 4$$

因此 ABAB 不是好字符串。

2. AABB 可以这样配对： 第 $1$ 个字符 A 和第 $2$ 个字符 A 配对； 第 $3$ 个字符 B 和第 $4$ 个字符 B 配对。

位置： 1   2   3   4
字符： A   A   B   B

       ┌───┐   ┌───┐
       A   A   B   B

两条弧线没有交叉，因此 AABB 是好字符串。

3. ABBA 可以这样配对： 第 $1$ 个字符 A 和第 $4$ 个字符 A 配对； 第 $2$ 个字符 B 和第 $3$ 个字符 B 配对。

位置： 1   2   3   4
字符： A   B   B   A

       ┌───────────┐
       │           │
       A   B   B   A
           ┌───┐
           B   B

两条弧线是包含关系，没有交叉，因此 ABBA 是好字符串。 所以样例 #1 中共有 $2$ 个好字符串，答案为 2。

样例 #2 解释

输入的三个字符串为：

AAA
AA
AB

AAA 的长度为奇数，不可能把每个字符都两两配对，因此不是好字符串； AA 可以将两个 A 配对，因此是好字符串； AB 两个字符不同，无法配对，因此不是好字符串。 所以只有 $1$ 个好字符串，答案为 1。

样例 #3 解释

字符串为：

ABBABB

可以这样配对： 第 $1$ 个字符 A 和第 $4$ 个字符 A 配对； 第 $2$ 个字符 B 和第 $3$ 个字符 B 配对； 第 $5$ 个字符 B 和第 $6$ 个字符 B 配对。

位置： 1   2   3   4   5   6
字符： A   B   B   A   B   B

       ┌───────────┐   ┌───┐
       │           │   │   │
       A   B   B   A   B   B
           ┌───┐
           B   B

所有弧线都没有交叉，因此 ABBABB 是好字符串。 所以答案为 1。

数据范围

对于所有测试数据，满足： $1 \le N \le 100$； 每个字符串只包含字符 A 和 B； 每个字符串长度在 $2$ 到 $100000$ 之间； 所有字符串长度之和不超过 $1000000$。