У Пьера сегодня большие проблемы! Он отвечает за управление бронирования номеров для РУЦ (Размещение по Умеренной Цене) отеля и буквально недавно понял, что программное обеспечение бронирования содержит серьезный баг. Это создало прецендент перекрывания и неправильного назначения номеров. Пьер очень обеспокоен тем, что отель может быть перебронирован. Поскольку производитель программного обеспечения не является ни отзывчивым, ни компетентным человеком, то Пьер должен делать все сам, своевременно принимая контрмеры в случае необходимости.

К счастью, Пьер был в состоянии экспортировать все оригинальные заказы (в том числе коды бронирования и действительные даты заезда и выезда). Единственная информация, которая потерялась - это время бронирования, так что Пьер не знает приоритетов бронирования (первой заказана - первой обслужена). Используя имеющуюся информацию, не могли бы вы помочь Пьеру и сообщить ему распределение номеров используя минимальное количество комнат так, чтобы удовлетворить все заказы? Обратите внимание на то, что номер должен всегда быть убран перед повторным использованием. Так как Пьер не хочет рисковать, он просит Вас рассматривать только максимальное время уборки.

Входные данные

Первая строка содержит количество t (1 ≤ t ≤ 100) тестов. Первая строка каждого теста содержит два целых числа: количество бронирований b (1 ≤ b ≤ 5000) и время уборки c (0 ≤ c ≤ 360) (в минутах) для одной комнаты. Каждая из следующих b строк содержит код резервации (произвольная строка из букв и цифр до 20 символов) и даты прибытия и выезда для одного бронирования. Даты заданы в формате "**YYYY-MM-DD HH:MM**" (как указано в примере), годы резервирования варьируются от 2013 до 2016.

Выходные данные

Для каждого теста выведите в отдельной строке минимальное количество необходимых номеров. Помните о високосных годах, но игнорируйтре Летнее время.