시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB86231754.839%

문제

상근이는 고등학교에서 학생들을 가르치고 있다. 오늘은 학생들을 당일치기 여행을 보내려고 한다. 다만, 학생들이 커플이 되는 경우는 피하려고 한다.

상근이는 오랜 연구 끝에 두 학생이 커플이 될 확률이 낮은 기준을 알게되었다.

  • 키 차이가 40cm보다 많이 나야 한다
  • 성별이 같아야 한다
  • 좋아하는 음악 장르가 달라야 한다.
  • 좋아하는 스포츠가 같아야 한다. (서로 다른 팀의 팬일 확률이 높아 싸울 확률이 높기 때문에)

여행을 가는 학생들 중에서 아무나 두 명을 뽑았을 때, 위의 조건 중 적어도 하나를 만족해야 한다. 여행을 갈 수 있는 최대 학생의 수는 몇 명일까?

입력

입력은 여러 개의 테스트 케이스로 이루어져 있고, 첫째 줄에 그 개수 T ≤ 100가 주어진다.

각 테스트 케이스의 첫째 줄에는 학생의 수 N ≤ 500이 주어진다. 다음 N개 줄에는 각 학생의 정보가 주어지며, 정보는 다음과 같이 네 부분으로 이루어져 있다.

  • 학생의 키를 나타내는 정수 h (단위: cm)
  • 학생의 성별 문자 M 또는 F (남자: M, 여자: F)
  • 좋아하는 음악 장르를 나타내는 문자열
  • 좋아하는 스포츠를 나타내는 문자열

모든 문자열은 100글자를 넘지 않으며, 공백을 포함하지 않는다.

출력

각 테스트 케이스마다 최대 몇 명이 여행을 갈 수 있는지 출력한다.

예제 입력 1

2
4
35 M classicism programming
0 M baroque skiing
43 M baroque chess
30 F baroque soccer
8
27 M romance programming
194 F baroque programming
67 M baroque ping-pong
51 M classicism programming
80 M classicism Paintball
35 M baroque ping-pong
39 F romance ping-pong
110 M romance Paintball

예제 출력 1

3
7
W3sicHJvYmxlbV9pZCI6IjM3MTMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIyZjlcdWM3N2NcdWNlNThcdWFlMzAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWFjZTBcdWI0ZjFcdWQ1NTlcdWFkNTBcdWM1ZDBcdWMxMWMgXHVkNTU5XHVjMGRkXHViNGU0XHVjNzQ0IFx1YWMwMFx1Yjk3NFx1Y2U1OFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YzYyNFx1YjI5OFx1Yzc0MCBcdWQ1NTlcdWMwZGRcdWI0ZTRcdWM3NDQgXHViMmY5XHVjNzdjXHVjZTU4XHVhZTMwIFx1YzVlY1x1ZDU4OVx1Yzc0NCBcdWJjZjRcdWIwYjRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWIyZTRcdWI5Y2MsIFx1ZDU1OVx1YzBkZFx1YjRlNFx1Yzc3NCBcdWNlZTRcdWQ1MGNcdWM3NzQgXHViNDE4XHViMjk0IFx1YWNiZFx1YzZiMFx1YjI5NCBcdWQ1M2NcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjNjI0XHViNzljIFx1YzVmMFx1YWQ2YyBcdWIwNWRcdWM1ZDAgXHViNDUwIFx1ZDU1OVx1YzBkZFx1Yzc3NCBcdWNlZTRcdWQ1MGNcdWM3NzQgXHViNDIwIFx1ZDY1NVx1Yjk2MFx1Yzc3NCBcdWIwYWVcdWM3NDAgXHVhZTMwXHVjOTAwXHVjNzQ0IFx1YzU0Y1x1YWM4Y1x1YjQxOFx1YzVjOFx1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5cdWQwYTQgXHVjYzI4XHVjNzc0XHVhYzAwIDQwY21cdWJjZjRcdWIyZTQgXHViOWNlXHVjNzc0IFx1YjA5OFx1YzU3YyBcdWQ1NWNcdWIyZTQ8XC9saT5cclxuXHQ8bGk+XHVjMTMxXHViY2M0XHVjNzc0IFx1YWMxOVx1YzU0NFx1YzU3YyBcdWQ1NWNcdWIyZTQ8XC9saT5cclxuXHQ8bGk+XHVjODhiXHVjNTQ0XHVkNTU4XHViMjk0IFx1Yzc0Y1x1YzU0NSBcdWM3YTVcdWI5NzRcdWFjMDAgXHViMmVjXHViNzdjXHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVjODhiXHVjNTQ0XHVkNTU4XHViMjk0IFx1YzJhNFx1ZDNlY1x1Y2UyMFx1YWMwMCBcdWFjMTlcdWM1NDRcdWM1N2MgXHVkNTVjXHViMmU0LiAoXHVjMTFjXHViODVjIFx1YjJlNFx1Yjk3OCBcdWQzMDBcdWM3NTggXHVkMzJjXHVjNzdjIFx1ZDY1NVx1Yjk2MFx1Yzc3NCBcdWIxOTJcdWM1NDQgXHVjMmY4XHVjNmI4IFx1ZDY1NVx1Yjk2MFx1Yzc3NCBcdWIxOTJcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwKTxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1YzVlY1x1ZDU4OVx1Yzc0NCBcdWFjMDBcdWIyOTQgXHVkNTU5XHVjMGRkXHViNGU0IFx1YzkxMVx1YzVkMFx1YzExYyBcdWM1NDRcdWJiMzRcdWIwOTggXHViNDUwIFx1YmE4NVx1Yzc0NCBcdWJmNTFcdWM1NThcdWM3NDQgXHViNTRjLCBcdWM3MDRcdWM3NTggXHVjODcwXHVhYzc0IFx1YzkxMSBcdWM4MDFcdWM1YjRcdWIzYzQgXHVkNTU4XHViMDk4XHViOTdjIFx1YjljY1x1Yzg3MVx1ZDU3NFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YzVlY1x1ZDU4OVx1Yzc0NCBcdWFjMDggXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWNkNWNcdWIzMDAgXHVkNTU5XHVjMGRkXHVjNzU4IFx1YzIxOFx1YjI5NCBcdWJhODcgXHViYTg1XHVjNzdjXHVhZTRjPzxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwLCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YWRmOCBcdWFjMWNcdWMyMTggVCAmbGU7IDEwMFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVkNTU5XHVjMGRkXHVjNzU4IFx1YzIxOCBOICZsZTsgNTAwXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIE5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWQ1NTlcdWMwZGRcdWM3NTggXHVjODE1XHViY2Y0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwgXHVjODE1XHViY2Y0XHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NzQgXHViMTI0IFx1YmQ4MFx1YmQ4NFx1YzczY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPlx1ZDU1OVx1YzBkZFx1Yzc1OCBcdWQwYTRcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YzgxNVx1YzIxOCBoIChcdWIyZThcdWM3MDQ6IGNtKTxcL2xpPlxyXG5cdDxsaT5cdWQ1NTlcdWMwZGRcdWM3NTggXHVjMTMxXHViY2M0IFx1YmIzOFx1Yzc5MCBNIFx1YjYxMFx1YjI5NCBGIChcdWIwYThcdWM3OTA6IE0sIFx1YzVlY1x1Yzc5MDogRik8XC9saT5cclxuXHQ8bGk+XHVjODhiXHVjNTQ0XHVkNTU4XHViMjk0IFx1Yzc0Y1x1YzU0NSBcdWM3YTVcdWI5NzRcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI0XHViMjk0IFx1YmIzOFx1Yzc5MFx1YzVmNDxcL2xpPlxyXG5cdDxsaT5cdWM4OGJcdWM1NDRcdWQ1NThcdWIyOTQgXHVjMmE0XHVkM2VjXHVjZTIwXHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWJiMzhcdWM3OTBcdWM1ZjQ8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWJhYThcdWI0ZTAgXHViYjM4XHVjNzkwXHVjNWY0XHVjNzQwIDEwMFx1YWUwMFx1Yzc5MFx1Yjk3YyBcdWIxMThcdWM5YzAgXHVjNTRhXHVjNzNjXHViYTcwLCBcdWFjZjVcdWJjMzFcdWM3NDQgXHVkM2VjXHVkNTY4XHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCBcdWNkNWNcdWIzMDAgXHViYTg3IFx1YmE4NVx1Yzc3NCBcdWM1ZWNcdWQ1ODlcdWM3NDQgXHVhYzA4IFx1YzIxOCBcdWM3ODhcdWIyOTRcdWM5YzAgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjM3MTMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJHdWFyZGlhbiBvZiBEZWNlbmN5IiwiZGVzY3JpcHRpb24iOiI8cD5GcmFuayBOLiBTdGVpbiBpcyBhIHZlcnkgY29uc2VydmF0aXZlIGhpZ2gtc2Nob29sIHRlYWNoZXIuIEhlIHdhbnRzIHRvIHRha2Ugc29tZSBvZiBoaXMgc3R1ZGVudHMgb24gYW4gZXhjdXJzaW9uLCBidXQgaGUgaXMgYWZyYWlkIHRoYXQgc29tZSBvZiB0aGVtIG1pZ2h0IGJlY29tZSBjb3VwbGVzLiBXaGlsZSB5b3UgY2FuIG5ldmVyIGV4Y2x1ZGUgdGhpcyBwb3NzaWJpbGl0eSwgaGUgaGFzIG1hZGUgc29tZSBydWxlcyB0aGF0IGhlIHRoaW5rcyBpbmRpY2F0ZXMgYSBsb3cgcHJvYmFiaWxpdHkgdHdvIHBlcnNvbnMgd2lsbCBiZWNvbWUgYSBjb3VwbGU6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+VGhlaXIgaGVpZ2h0IGRpZmZlcnMgYnkgbW9yZSB0aGFuIDQwIGNtLjxcL2xpPlxyXG5cdDxsaT5UaGV5IGFyZSBvZiB0aGUgc2FtZSBzZXguPFwvbGk+XHJcblx0PGxpPlRoZWlyIHByZWZlcnJlZCBtdXNpYyBzdHlsZSBpcyBkaWZmZXJlbnQuPFwvbGk+XHJcblx0PGxpPlRoZWlyIGZhdm91cml0ZSBzcG9ydCBpcyB0aGUgc2FtZSAodGhleSBhcmUgbGlrZWx5IHRvIGJlIGZhbnMgb2YgZGlmZmVyZW50IHRlYW1zIGFuZCB0aGF0IHdvdWxkIHJlc3VsdCBpbiBcdWZiMDFnaHRpbmcpLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlNvLCBmb3IgYW55IHR3byBwZXJzb25zIHRoYXQgaGUgYnJpbmdzIG9uIHRoZSBleGN1cnNpb24sIHRoZXkgbXVzdCBzYXRpc2Z5IGF0IGxlYXN0IG9uZSBvZiB0aGUgcmVxdWlyZW1lbnRzIGFib3ZlLiBIZWxwIGhpbSBcdWZiMDFuZCB0aGUgbWF4aW11bSBudW1iZXIgb2YgcGVyc29ucyBoZSBjYW4gdGFrZSwgZ2l2ZW4gdGhlaXIgdml0YWwgaW5mb3JtYXRpb24uPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgXHVmYjAxcnN0IGxpbmUgb2YgdGhlIGlucHV0IGNvbnNpc3RzIG9mIGFuIGludGVnZXIgVCAmbGU7IDEwMCBnaXZpbmcgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzLiBUaGUgXHVmYjAxcnN0IGxpbmUgb2YgZWFjaCB0ZXN0IGNhc2UgY29uc2lzdHMgb2YgYW4gaW50ZWdlciBOICZsZTsgNTAwIGdpdmluZyB0aGUgbnVtYmVyIG9mIHB1cGlscy4gTmV4dCB0aGVyZSB3aWxsIGJlIG9uZSBsaW5lIGZvciBlYWNoIHB1cGlsIGNvbnNpc3Rpbmcgb2YgZm91ciBzcGFjZS1zZXBhcmF0ZWQgZGF0YSBpdGVtczo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5hbiBpbnRlZ2VyIGggZ2l2aW5nIHRoZSBoZWlnaHQgaW4gY207PFwvbGk+XHJcblx0PGxpPmEgY2hhcmFjdGVyICZyc3F1bztGJnJzcXVvOyBmb3IgZmVtYWxlIG9yICZyc3F1bztNJnJzcXVvOyBmb3IgbWFsZTs8XC9saT5cclxuXHQ8bGk+YSBzdHJpbmcgZGVzY3JpYmluZyB0aGUgcHJlZmVycmVkIG11c2ljIHN0eWxlOzxcL2xpPlxyXG5cdDxsaT5hIHN0cmluZyB3aXRoIHRoZSBuYW1lIG9mIHRoZSBmYXZvdXJpdGUgc3BvcnQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+Tm8gc3RyaW5nIGluIHRoZSBpbnB1dCB3aWxsIGNvbnRhaW4gbW9yZSB0aGFuIDEwMCBjaGFyYWN0ZXJzLCBub3Igd2lsbCBhbnkgc3RyaW5nIGNvbnRhaW4gYW55IHdoaXRlc3BhY2UuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlIGluIHRoZSBpbnB1dCB0aGVyZSBzaG91bGQgYmUgb25lIGxpbmUgd2l0aCBhbiBpbnRlZ2VyIGdpdmluZyB0aGUgbWF4aW11bSBudW1iZXIgb2YgZWxpZ2libGUgcHVwaWxzLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2005 H번