시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 3 3 2 100.000%

문제

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

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

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

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

입력

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

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

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

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

출력

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

예제 입력

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

예제 출력

3
7

힌트