e-olymp
Задачі

Любитель порядку

Любитель порядку

Франк Енштейн - дуже консервативний вчитель середньої школи. Він хоче взяти деяких зі своїх учнів на екскурсію, але переживає, що деякі з них можуть стати конфліктною або закоханою парою. Щоб виключити таку можливість, він придумав ряд правил, які на його думку зменшують ймовірність двом школярам утворити таку пару:

  • Різниця у зрості повинна перевищувати 40 см.
  • Вони повинні бути одної статі.
  • Вони повинні любити різні стилі музики.
  • Їх любимий вид спорту - один і той же.

Таким чином, для довільних двох учнів, які він візьме на екскурсію, вони повинні відповідати, по меншій міре, одній з вишевказаних вимог. Допоможіть йому знайти максимальну кількість учнів, які він може взяти на екскурсію, враховуючи інформацію про них.

Вхідні дані

У першому рядку задано число Т100 - кількість тестів. Перший рядок кожного теста складається з цілого числа N500 - кількість учнів у школі. Наступні рядки описують кожного учня і складаються з чотирьох, відокремлених пропусками елементів даних:

  • ціле число h ­­- зріст в см;
  • символ 'F' для жінок, або "М" для чоловіків;
  • слово, що описує бажаний стиль музыки;
  • слово с іменем любимого виду спорту.

Кожен рядок містить не більше 100 символів, у вхідних даних немає пустих рядків.

Вихідні дані

Для кожного тесту на виході повинен бути один рядок з шуканою максимальною кількістю учнів, які вчитель може взяти на екскурсію.

Ліміт часу 2 секунди
Ліміт використання пам'яті 64 MiB
Вхідні дані #1
1
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
Вихідні дані #1
7