호텔 예약

정인이는 Top Root 호텔에서 예약을 관리한다. 오늘 정인이는 예약 관리 소프트웨어에서 버그를 찾아냈다. 이 버그 탓에 같은 방이 겹쳐서 예약되고 손님이 엉뚱한 방에 배정되는 일이 벌어졌다. 소프트웨어를 만든 회사는 이미 망했다. 그래서 정인이는 버그를 직접 고치고 대책을 세우기로 했다.

정인이는 먼저 예약 정보를 모두 내보냈다. 예약 하나에는 예약 코드와 입실 시각, 퇴실 시각이 들어 있다. 이 정보대로 모든 예약에 방을 배정하려면 방이 최소 몇 개 필요한지 구하는 프로그램을 작성하시오.

한 번 쓴 방은 청소를 마쳐야 다시 쓸 수 있다. 정인이는 위험을 감수하지 않으므로 청소에 걸리는 시간을 언제나 최대 청소 시간 $C$분으로 잡는다. 즉 퇴실 시각이 $t$인 방은 $t + C$부터 다음 손님을 받을 수 있고, 정확히 $t + C$에 입실하는 예약은 그 방을 그대로 쓸 수 있다.

첫째 줄에 테스트 케이스의 개수 $T$ ($1 \le T \le 100$)가 주어진다.

각 테스트 케이스의 첫째 줄에는 예약의 수 $B$ ($1 \le B \le 5000$)와 방 하나를 청소하는 데 걸리는 시간 $C$ ($0 \le C \le 360$)가 공백으로 구분되어 주어진다. $C$의 단위는 분이다.

이어지는 $B$개 줄에는 예약 정보가 한 줄에 하나씩 주어진다. 각 줄은 예약 코드, 입실 시각, 퇴실 시각 순이다. 예약 코드는 알파벳과 숫자로만 이루어진 길이 20 이하의 문자열이다. 시각은 YYYY-MM-DD HH:MM 형식이고, 2013년부터 2016년 사이의 예약만 주어진다.

각 테스트 케이스마다 필요한 방의 최소 개수를 한 줄에 하나씩 출력한다.

윤년을 반드시 고려해야 한다. 일광 절약 시간제는 고려하지 않는다.