Бронювання
У П'єра сьогодні великі проблеми! Він відповідає за управління бронюванням номерів у готелі РУЦ (Розміщення за Умереною Ціною) і нещодавно виявив серйозну помилку в програмному забезпеченні для бронювання. Це призвело до накладок і неправильного призначення номерів. П'єр дуже стурбований можливістю перебронювання готелю. Оскільки виробник програмного забезпечення не відповідає на запити і не є компетентним, П'єру доводиться вирішувати проблему самостійно, вживаючи необхідних заходів.
На щастя, П'єр зміг експортувати всі оригінальні замовлення, включаючи коди бронювання та дати заїзду і виїзду. Єдина втрата — це час бронювання, тому П'єр не знає пріоритетів (хто перший забронював, той перший обслуговується). Використовуючи наявну інформацію, чи можете ви допомогти П'єру визначити розподіл номерів, використовуючи мінімальну кількість кімнат, щоб задовольнити всі замовлення? Зверніть увагу, що номер завжди повинен бути прибраний перед повторним використанням. Оскільки П'єр не хоче ризикувати, він просить враховувати максимальний час прибирання.
Вхідні дані
Перша стрічка містить кількість t (1 ≤ t ≤ 100) тестів. Перша стрічка кожного тесту містить два цілі числа: кількість бронювань b (1 ≤ b ≤ 5000) і час прибирання c (0 ≤ c ≤ 360) (у хвилинах) для однієї кімнати. Кожен з наступних b рядків містить код резервації (довільний рядок з літер і цифр до 20 символів) і дати прибуття та виїзду для одного бронювання. Дати задані у форматі "YYYY-MM-DD HH:MM" (як вказано в прикладі), роки резервування варіюються від 2013 до 2016.
Вихідні дані
Для кожного тесту виведіть в окремому рядку мінімальну кількість необхідних номерів. Пам'ятайте про високосні роки, але ігноруйте Літній час.