시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 2491 1059 890 45.316%

문제

이번 계절학기에 심리학 개론을 수강 중인 평석이는 오늘 자정까지 보고서를 제출해야 한다. 보고서 작성이 너무 지루했던 평석이는 노트북에 엎드려서 꾸벅꾸벅 졸다가 제출 마감 1시간 전에 깨고 말았다. 안타깝게도 자는 동안 키보드가 잘못 눌려서 보고서의 모든 글자가 A와 B로 바뀌어 버렸다! 그래서 평석이는 보고서 작성을 때려치우고 보고서에서 '좋은 단어'나 세보기로 마음 먹었다.

평석이는 단어 위로 아치형 곡선을 그어 같은 글자끼리(A는 A끼리, B는 B끼리) 쌍을 짓기로 하였다. 만약 선끼리 교차하지 않으면서 각 글자를 정확히 한 개의 다른 위치에 있는 같은 글자와 짝 지을수 있다면, 그 단어는 '좋은 단어'이다. 평석이가 '좋은 단어' 개수를 세는 것을 도와주자.

입력

첫째 줄에 단어의 수 N이 주어진다. (1 ≤ N ≤ 100)

다음 N개 줄에는 A와 B로만 이루어진 단어가 한 줄에 하나씩 주어진다. 단어의 길이는 2와 100,000사이이며, 모든 단어 길이의 합은 1,000,000을 넘지 않는다.

출력

첫째 줄에 좋은 단어의 수를 출력한다.

예제 입력 1

3
ABAB
AABB
ABBA

예제 출력 1

2
W3sicHJvYmxlbV9pZCI6IjM5ODYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4OGJcdWM3NDAgXHViMmU4XHVjNWI0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM3NzRcdWJjODggXHVhY2M0XHVjODA4XHVkNTU5XHVhZTMwXHVjNWQwIFx1YzJlY1x1YjlhY1x1ZDU1OSBcdWFjMWNcdWI4NjBcdWM3NDQgXHVjMjE4XHVhYzE1IFx1YzkxMVx1Yzc3OCBcdWQzYzlcdWMxMWRcdWM3NzRcdWIyOTQgXHVjNjI0XHViMjk4IFx1Yzc5MFx1YzgxNVx1YWU0Y1x1YzljMCBcdWJjZjRcdWFjZTBcdWMxMWNcdWI5N2MgXHVjODFjXHVjZDljXHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHViY2Y0XHVhY2UwXHVjMTFjIFx1Yzc5MVx1YzEzMVx1Yzc3NCBcdWIxMDhcdWJiMzQgXHVjOWMwXHViOGU4XHVkNTg4XHViMzU4IFx1ZDNjOVx1YzExZFx1Yzc3NFx1YjI5NCBcdWIxNzhcdWQyYjhcdWJkODFcdWM1ZDAgXHVjNWNlXHViNGRjXHViODI0XHVjMTFjIFx1YWZiOFx1YmM4NVx1YWZiOFx1YmM4NSBcdWM4NzhcdWIyZTRcdWFjMDAgXHVjODFjXHVjZDljIFx1YjljOFx1YWMxMCAxXHVjMmRjXHVhYzA0IFx1YzgwNFx1YzVkMCBcdWFlNjhcdWFjZTAgXHViOWQwXHVjNTU4XHViMmU0LiBcdWM1NDhcdWQwYzBcdWFlNWRcdWFjOGNcdWIzYzQgXHVjNzkwXHViMjk0IFx1YjNkOVx1YzU0OCBcdWQwYTRcdWJjZjRcdWI0ZGNcdWFjMDAgXHVjNzk4XHViYWJiIFx1YjIwY1x1YjgyNFx1YzExYyBcdWJjZjRcdWFjZTBcdWMxMWNcdWM3NTggXHViYWE4XHViNGUwIFx1YWUwMFx1Yzc5MFx1YWMwMCBBXHVjNjQwIEJcdWI4NWMgXHViYzE0XHViMDBjXHVjNWI0IFx1YmM4NFx1YjgzOFx1YjJlNCEgXHVhZGY4XHViNzk4XHVjMTFjIFx1ZDNjOVx1YzExZFx1Yzc3NFx1YjI5NCBcdWJjZjRcdWFjZTBcdWMxMWMgXHVjNzkxXHVjMTMxXHVjNzQ0IFx1YjU0Y1x1YjgyNFx1Y2U1OFx1YzZiMFx1YWNlMCBcdWJjZjRcdWFjZTBcdWMxMWNcdWM1ZDBcdWMxMWMgJiMzOTtcdWM4OGJcdWM3NDAgXHViMmU4XHVjNWI0JiMzOTtcdWIwOTggXHVjMTM4XHViY2Y0XHVhZTMwXHViODVjIFx1YjljOFx1Yzc0YyBcdWJhMzlcdWM1YzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDNjOVx1YzExZFx1Yzc3NFx1YjI5NCBcdWIyZThcdWM1YjQgXHVjNzA0XHViODVjIFx1YzU0NFx1Y2U1OFx1ZDYxNSBcdWFjZTFcdWMxMjBcdWM3NDQgXHVhZGY4XHVjNWI0IFx1YWMxOVx1Yzc0MCBcdWFlMDBcdWM3OTBcdWIwN2NcdWI5YWMoQVx1YjI5NCBBXHViMDdjXHViOWFjLCBCXHViMjk0IEJcdWIwN2NcdWI5YWMpIFx1YzMwZFx1Yzc0NCBcdWM5ZDNcdWFlMzBcdWI4NWMgXHVkNTU4XHVjNjAwXHViMmU0LiBcdWI5Y2NcdWM1N2QgXHVjMTIwXHViMDdjXHViOWFjIFx1YWQ1MFx1Y2MyOFx1ZDU1OFx1YzljMCBcdWM1NGFcdWM3M2NcdWJhNzRcdWMxMWMgXHVhYzAxIFx1YWUwMFx1Yzc5MFx1Yjk3YyBcdWM4MTVcdWQ2NTVcdWQ3ODggXHVkNTVjIFx1YWMxY1x1Yzc1OCBcdWIyZTRcdWI5NzggXHVjNzA0XHVjZTU4XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWFjMTlcdWM3NDAgXHVhZTAwXHVjNzkwXHVjNjQwIFx1YzlkZCBcdWM5YzBcdWM3NDRcdWMyMTggXHVjNzg4XHViMmU0XHViYTc0LCBcdWFkZjggXHViMmU4XHVjNWI0XHViMjk0ICYjMzk7XHVjODhiXHVjNzQwIFx1YjJlOFx1YzViNCYjMzk7XHVjNzc0XHViMmU0LiBcdWQzYzlcdWMxMWRcdWM3NzRcdWFjMDAgJiMzOTtcdWM4OGJcdWM3NDAgXHViMmU4XHVjNWI0JiMzOTsgXHVhYzFjXHVjMjE4XHViOTdjIFx1YzEzOFx1YjI5NCBcdWFjODNcdWM3NDQgXHViM2M0XHVjNjQwXHVjOGZjXHVjNzkwLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWIyZThcdWM1YjRcdWM3NTggXHVjMjE4IE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE4gJmxlOyAxMDApPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBOXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBBXHVjNjQwIEJcdWI4NWNcdWI5Y2MgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YjJlOFx1YzViNFx1YWMwMCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlOFx1YzViNFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWIyOTQgMlx1YzY0MCAxMDAsMDAwXHVjMGFjXHVjNzc0XHVjNzc0XHViYTcwLCBcdWJhYThcdWI0ZTAgXHViMmU4XHVjNWI0IFx1YWUzOFx1Yzc3NFx1Yzc1OCBcdWQ1NjlcdWM3NDAgMSwwMDAsMDAwXHVjNzQ0IFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM4OGJcdWM3NDAgXHViMmU4XHVjNWI0XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzk4NiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkVTRUoiLCJkZXNjcmlwdGlvbiI6IjxwPk1pcmtvJiMzOTtzIGxhdGVzdCBob21ld29yayBhc3NpZ25tZW50IGlzIHdyaXRpbmcgYW4gZXNzYXkuIEhvd2V2ZXIsIGhlIGZpbmRzIHdyaXRpbmcgZXNzYXlzIHNvIGJvcmluZyB0aGF0LCBhZnRlciB3b3JraW5nIGZvciB0d28gaG91cnMsIGhlIHJlYWxpemVkIHRoYXQgYWxsIGhlIGhhcyB3cml0dGVuIGFyZSBOIGxvbmcgd29yZHMgY29uc2lzdGluZyBlbnRpcmVseSBvZiBsZXR0ZXJzIEEgYW5kIEIuIEhhdmluZyBhY2NlcHRlZCB0aGF0IGhlIHdpbGwgbmV2ZXIgZmluaXNoIHRoZSBlc3NheSBpbiB0aW1lLCBwb29yIE1pcmtvIGhhcyBkZWNpZGVkIHRvIGF0IGxlYXN0IGhhdmUgc29tZSBmdW4gd2l0aCBpdCBieSBjb3VudGluZyBuaWNlIHdvcmRzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5NaXJrbyBpcyBjb25uZWN0aW5nIHBhaXJzIG9mIGlkZW50aWNhbCBsZXR0ZXJzIChBIHdpdGggQSwgQiB3aXRoIEIpIGJ5IGRyYXdpbmcgYXJjaGVzIGFib3ZlIHRoZSB3b3JkLiBBIGdpdmVuIHdvcmQgaXMgbmljZSBpZiBlYWNoIGxldHRlciBjYW4gYmUgY29ubmVjdGVkIHRvIGV4YWN0bHkgb25lIG90aGVyIGxldHRlciBpbiBzdWNoIGEgd2F5IHRoYXQgbm8gdHdvIGFyY2hlcyBpbnRlcnNlY3QuIEhlbHAgTWlya28gY291bnQgaG93IG1hbnkgd29yZHMgYXJlIG5pY2UuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aGUgcG9zaXRpdmUgaW50ZWdlciBOICgxICZsZTsgTiAmbGU7IDEwMCksIHRoZSBudW1iZXIgb2Ygd29yZHMgd3JpdHRlbiBkb3duIGJ5IE1pcmtvLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBmb2xsb3dpbmcgTiBsaW5lcyBjb250YWlucyBhIHNpbmdsZSB3b3JkIGNvbnNpc3Rpbmcgb2YgbGV0dGVycyBBIGFuZCBCLCB3aXRoIGxlbmd0aCBiZXR3ZWVuIDIgYW5kIDEwMCAwMDAsIGluY2x1c2l2ZS4gVGhlIHN1bSBvZiBsZW5ndGhzIG9mIGFsbCB3b3JkcyBkb2VzbiYjMzk7dCBleGNlZWQgMSAwMDAgMDAwLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBtdXN0IGNvbnRhaW4gdGhlIG51bWJlciBvZiBuaWNlIHdvcmRzLiZuYnNwOzxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=