[요약 중] 미코는 에세이를 쓰고 있다. 그런데 이 일이 너무 지루한 작업이라 두 시간 동안 일한 후 그가 쓴 것이 N 만큼 길고 모두 A,B 로만 이루어져 있다는 것을 알았다. 제 시간에 모두 마칠수 없다는 것을 안 가련한 미코는 멋진 단어를 세면서 놀기로 하였다.

단어위 같은 문자에 호를 그리는 놀이이다. 호가 교차되지 않고 그릴수 있으면 이 단어는 나이스 하다고 한다. 나이스한 단어의 수를 구하는 것이 문제이다.

첫 번째 입력 예시이다.

Mirko is connecting pairs of identical letters (A with A, B with B) by drawing arches above the word. A given word is nice if each letter can be connected to exactly one other letter in such a way that no two arches intersect. Help Mirko count how many words are nice.

입력

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

출력

입출력 예

input 

3 
ABAB 
AABB 
ABBA 

output 

2 

input 

3 
AAA 
AA 
AB 

output 

1 

input 

1 
ABBABB 

output 

1

출처:coci/2012-2013/contest4 2번