문제 설명
민철이는 이번 학년 마지막 숙제로 실험 보고서를 써야한다. 그런데 이 실험 보고서는 쓸 내용만 많고 생각할 만한 것들이 별로 없어 너무 지루했고, 민철이는 결국 졸고 말았다. 민철이가 정신을 차렸을 때 보고서는 A와 B만 남게 되었다. 조는 동안 잘못 눌려 모든 내용이 날라가고 A와 B만 새로 써졌고, 민철이는 제출까지 남은 2시간 안에 실험 보고서를 쓰는 것은 불가능해서 그냥 맘 편히 A와 B로 만들어진 멋진 단어나 세며 놀기로 마음먹었다.
민철이는 같은 문자끼리 아치형 곡선을 연결하여 쌍을 만들고, 이 곡선들이 서로 교차하지 않으면서 모든 문자가 짝을 이룬다면 그 단어는 멋진 단어이다.
민철이를 도와 멋진 단어가 몇 개인지 세주는 프로그램을 작성하시오.
입력 설명
첫 번째 줄에 단어의 개수 N(1 ≤ N ≤ 100)이 주어진다.
다음 N개의 줄에 걸쳐 A와 B만으로 이루어진 단어가 주어지며 단어의 길이는 2이상 100,000이하이다. 또한 모든 단어의 길이를 합해도 1,000,000을 넘지 않는다.