Banh đang làm bài tập về nhà, nhưng cậu ấy thấy việc viết bài luận thật nhàm chán. Sau hai giờ làm việc, cậu nhận ra rằng tất cả những gì cậu đã viết chỉ là $N$ từ dài, mỗi từ chỉ bao gồm các chữ cái A và B. Nhận thấy rằng cậu sẽ không kịp hoàn thành bài luận, Yuuki quyết định ít nhất sẽ tìm chút vui trong đó bằng cách đếm số từ "đẹp".
Banh kết nối các cặp chữ cái giống nhau (A với A, B với B) bằng cách vẽ những cung cong phía trên từ. Một từ được gọi là "đẹp" nếu mỗi chữ cái có thể được kết nối với đúng một chữ cái khác sao cho không có hai cung cong nào cắt nhau.
Hãy giúp Banh đếm xem có bao nhiêu từ là "đẹp".
Input:

• Dòng đầu tiên của đầu vào chứa số nguyên dương $n$ ($1 \leq n \leq 100$), số từ mà Banh đã viết.
• Mỗi dòng trong N dòng sau chứa một từ duy nhất gồm các chữ cái A và B, có độ dài từ 2 đến 100 000, bao gồm cả hai.
• Tổng độ dài của tất cả các từ không vượt quá 1 000 000.

Output:

• Dòng đầu tiên và duy nhất của đầu ra phải chứa số lượng từ "đẹp".

Example:

3
ABAB
AABB
ABBA 

 2

3
AAA
AA
AB

 1

1
ABBABB 

 1        

Scoring:

• Subtask 1: Với 50% số điểm: $N \leq 100$
• Subtask 2: Với 50% số điểm: Không có ràng buộc gì thêm