Good Words

Time limit1sMemory limit256 MB

Summary

A word of A's and B's is good when its letters can be paired by equal letters with non-crossing arcs; count how many of the given words are good.

Level: Medium5 of 10
Topics: Stack, String, Greedy, Implementation
Solved: No attempts yet

Problem

Pyeongseok, who is taking Introduction to Psychology in this seasonal (intersession) term, has to submit a report by midnight tonight. Writing the report was so boring that he dozed off face-down on his laptop and woke up only one hour before the deadline. To his dismay, while he was asleep the keyboard got pressed by mistake and every single letter of his report had turned into an A or a B! So Pyeongseok gave up on the report and decided to count the "good words" in it instead.

Pyeongseok pairs up equal letters (A with A, B with B) by drawing arch-shaped curves over the word. If every letter can be paired with exactly one other equal letter at a different position so that no two arcs cross, the word is a "good word". Help Pyeongseok count the number of good words.

Input

The first line contains the number of words $N$ ( $1 \le N \le 100$ ).

Each of the next $N$ lines contains one word made up only of the letters A and B. Each word has length between $2$ and $100\,000$ , and the total length of all words does not exceed $1\,000\,000$ .

Output

Print the number of good words on the first line.

Examples3

Example 1
Input
```
3
ABAB
AABB
ABBA
```
Expected output
```
2
```
Example 2
Input
```
3
AAA
AA
AB
```
Expected output
```
1
```
Example 3
Input
```
1
ABBABB
```
Expected output
```
1
```