Nice Arches

Nikki's latest work is writing a story of letters. However, she finds writing the story so boring that, after working for three hours, she realized that all she has written are M long words consisting entirely of letters A and B. Having accepted that she will never finish the story in time, poor Nikki has decided to at least have some fun with it by counting bubbly words.

Now Nikki is connecting pairs of identical letters (A with A, B with B) by drawing arches above the word. A given word is bubbly if it is possible to connect each letter to exactly one other letter in such a way that no two arches intersect. So here is your task. Help Nikki count how many words are bubbly.

Input Specification

The first line of the input contains a positive integer M, the number of words written down by Nikki (1 ≤ M ≤ 100). Each of the following M lines contains a single word consisting of letters A and B, with length between 2 and 10⁵, inclusive. The sum of the lengths of all words doesn't exceed 10⁶.

Output Specification

The first and only line of output must contain the number of bubbly words.

Sample Input

1. 3
2. ABAB
3. AABB
4. ABBA

download as text file

Output for Sample Input

1. 2

download as text file

Sample Explanation

ABAB — It is not bubbly, as A (indexed 1) will connect to A (indexed 3) by an arch, and when we try to connect B (indexed 2) with B (indexed 4) by an arch, then it will intersect with the arch between A and A. AABB — It is bubbly, as the arch between A and A will not intersect with the arch between B and B. ABBA — It is also bubbly, as arches will not intersect: we can draw the arch between A and A above the arch between B and B.