Day Trip

Time limit1sMemory limit128 MB

Summary

Select the largest subset of students so every pair differs by more than 40cm in height, or shares gender, or differs in music genre, or shares sport, which reduces to a maximum independent set style selection solvable via clever graph structuring.

Level: Medium7 of 10
Topics: Graph, Greedy, Sorting
Solved: No attempts yet

Problem

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.

Input

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.

Output

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

Examples5

Example 1

Input

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

Expected output

3
7

Example 2
Input
```
1
1
170 M rock soccer
```
Expected output
```
1
```

Example 3

Input

1
2
100 M jazz tennis
120 F jazz soccer

Expected output

Example 4

Input

1
2
100 M jazz tennis
150 F jazz soccer

Expected output

Example 5

Input

1
2
100 M jazz tennis
110 M jazz soccer

Expected output