Guardian of Decency#433
Frank N. Stein is a very conservative high-school teacher. He wants to take some of his students on an excursion, but he is afraid that some of them might become couples. While you can never exclude this possibility, he has made some rules that indicate a low probability two persons will become a couple:
Their height differs by more than cm.
They are of the same sex.
Their preferred music style is different.
Their favourite sport is the same.
So, for any two persons that he brings on the excursion, they must satisfy at least one of the requirements above. Help him find the maximum number of pupils he can take, given their vital information.
The first line contains an integer T \leq 100 — the number of test cases. The first line of each test case contains an integer N \leq 500 — the number of pupils. The next lines describe each pupil and consist of four space-separated data items:
an integer — the height in cm;
a character '' for female or '' for male;
a string describing the preferred music style;
a string with the name of the favourite sport.
No line in the input will contain more than characters, and there are no empty lines in the input.
For each test case, output one line containing the maximum number of pupils the teacher can bring on the excursion.
Example 1