당일치기

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

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

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

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

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

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

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

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

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