당일치기

시간 제한1초메모리 제한128 MB

요약
학생 두 명씩 짝지을 때 키 차이가 40cm 초과이거나 성별이 같거나 음악 장르가 다르거나 스포츠가 같아야 한다는 조건을 모두 만족하도록, 여행에 보낼 수 있는 학생 수를 최대화합니다.
난이도

보통10점 중 7점

유형
그래프, 그리디, 정렬
정답자
아직 제출이 없습니다

문제

상근이는 고등학교에서 학생들을 가르칩니다. 오늘은 학생들을 당일치기 여행에 보내려고 합니다. 다만 여행 중에 학생들이 커플이 되는 상황은 피하고 싶습니다.

상근이는 오랜 관찰 끝에, 두 학생이 커플이 될 확률이 낮아지는 다음 네 가지 기준을 알아냈습니다.

  • 두 사람의 키 차이가 40cm를 초과한다.
  • 두 사람의 성별이 같다.
  • 두 사람이 좋아하는 음악 장르가 서로 다르다.
  • 두 사람이 좋아하는 스포츠가 같다. (서로 다른 팀을 응원할 가능성이 커서 다툴 확률이 높기 때문입니다.)

여행을 가는 학생들 중에서 임의의 두 명을 골랐을 때, 위 네 가지 조건 중 적어도 하나가 성립해야 합니다. 이 조건을 만족시키면서 여행을 보낼 수 있는 학생 수의 최댓값을 구하세요.

입력

입력은 여러 개의 테스트 케이스로 이루어집니다. 첫째 줄에 테스트 케이스의 수 T≤100T \le 100 이 주어집니다.

각 테스트 케이스의 첫째 줄에는 학생 수 N≤500N \le 500 이 주어집니다. 이어지는 NN개의 줄에는 각 학생의 정보가 다음 네 부분으로 주어집니다.

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

모든 문자열은 길이가 100자를 넘지 않으며 공백을 포함하지 않습니다.

출력

각 테스트 케이스마다 여행을 보낼 수 있는 학생 수의 최댓값을 한 줄에 출력하세요.

예제5

  1. 예제 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
    예상 출력
    3
7

  2. 예제 2

    입력
    1
1
170 M rock soccer
    예상 출력
    1

  3. 예제 3

    입력
    1
2
100 M jazz tennis
120 F jazz soccer
    예상 출력
    1

  4. 예제 4

    입력
    1
2
100 M jazz tennis
150 F jazz soccer
    예상 출력
    2

  5. 예제 5

    입력
    1
2
100 M jazz tennis
110 M jazz soccer
    예상 출력
    2