You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

$cj$ 最近的家庭作业是写一篇作文。然而，他觉得写作文太无聊了，于是在写了两个小时后，他发现自己只写了 $N$ 个只由字母 $A$ 和 $B$ 组成的长单词。$cj$ 已经接受了自己无法按时完成作文的事实，于是他决定至少让自己在作文里找点乐趣，比如统计 “好单词” 的数量

Description。

$cj$ 会通过在单词上方画弧，将成对的相同字母（$A$ 对 $A$，$B$ 对 $B$）连接起来。如果一个单词满足：可以将每个字母与恰好一个相同字母配对，并且所有的弧都不会相交，那么这个单词就是“好单词”。 请帮助 $cj$ 统计有多少个“好单词”。

Format

Input

第一行输入一个正整数 $N$（$1 \leq N \leq 100$），表示 $Mirko$ 写下的单词数。

接下来的 $N$ 行，每行输入一个只包含字母 $A$ 和 $B$ 的单词，长度为 $len$ , ( $2\leq len \leq 10^6$ )。所有单词的总长度不超过 $10^6$。

Output

输出一行，表示“好单词”的数量。.

Samples

3
ABAB
AABB
ABBA

2

3
AAA
AA
AB

1

2

1
ABBABB

1

Limitation

1s, 1024KiB for each test case.