Любитель порядка
Франк Энштейн - очень консервативный учитель средней школы. Он хочет взять некоторых из своих учеников на экскурсию, но опасается, что некоторые из них могут стать конфликтной или влюбленной парой. Чтобы исключить такую возможность, он придумал ряд правил, которые по его мнению уменьшают вероятность двум людям образовать такую пару:
Разница в их росте должна превышать 40 см.
Они должны быть одного пола.
Они должны любить разные стили музыки.
Их любимый вид спорта - один и тот же.
Таким образом, для любых двух учеников, которых он возьмёт на экскурсию, они должны отвечать, по крайней мере, одному из вышеуказанных требований. Помогите ему найти максимальное число учеников, которые он может взять на экскурсию, учитывая информацию о них.
Входные данные
В первой строке задано число Т ≤ 100 - количество тестов. Первая строка каждого теста содержит целое число N ≤ 500 - количество учащихся в школе. Следующие строки описывают каждого ученика и состоят из четырех, разделенных пробелами, элементов данных:
Целое число h - рост в см;
символ 'F' для женщин, или "М" для мужчин;
слово, описывающее предпочтительный стиль музыки;
слово с именем любимого вида спорта.
Каждая строка содержит не более 100 символов, и во входных данных нет пустых строк.
Выходные данные
Для каждого теста на выходе должна быть одна строка с искомым максимальным количеством учащихся, которые учитель может взять на экскурсию.