Day Trip

Sanggeun teaches students at a high school. Today he wants to send the students on a day trip, but he would like to avoid any of them ending up as a couple during the trip.

After long observation, Sanggeun has found four criteria, any one of which makes it unlikely that two students become a couple:

• Their height difference is more than 40 cm.
• They have the same gender.
• They like different music genres.
• They like the same sport. (Fans of the same sport are likely to support different teams and are therefore more likely to argue.)

For any two students chosen among those who go on the trip, at least one of the four criteria above must hold. Find the maximum number of students that can be sent on the trip while satisfying this requirement.

The input consists of several test cases. The first line contains the number of test cases $T \le 100$.

The first line of each test case contains the number of students $N \le 500$. Each of the following $N$ lines describes one student with the following four parts:

• an integer $h$ giving the student's height (in cm),
• a character giving the student's gender (M for male, F for female),
• a string giving the student's favourite music genre,
• a string giving the student's favourite sport.

Every string is at most 100 characters long and contains no spaces.

For each test case, output on a single line the maximum number of students that can be sent on the trip.