Hotel Reservations

Jeongin manages the reservations at the Top Root Hotel. Today Jeongin found a bug in the reservation software. The bug booked the same room twice over and sent guests to the wrong rooms. The company that wrote the software is already out of business, so Jeongin decided to fix the bug and work out a plan.

Jeongin exported every reservation first. One reservation holds a reservation code, a check-in time and a check-out time. Write a program that finds the smallest number of rooms needed to place every reservation.

A room has to be cleaned before anyone uses it again. Jeongin takes no chances, so cleaning always takes the full maximum cleaning time of $C$ minutes. A room whose guest checks out at time $t$ is free from $t + C$ onward, and a reservation that checks in at exactly $t + C$ may use that room.

The first line contains the number of test cases $T$ ($1 \le T \le 100$).

The first line of each test case contains the number of reservations $B$ ($1 \le B \le 5000$) and the time $C$ ($0 \le C \le 360$) it takes to clean one room, separated by a space. $C$ is measured in minutes.

Each of the next $B$ lines describes one reservation, in the order reservation code, check-in time, check-out time. A reservation code is a string of at most 20 letters and digits. Times use the format YYYY-MM-DD HH:MM, and only reservations between 2013 and 2016 are given.

For each test case, print the minimum number of rooms on its own line.

Leap years have to be handled correctly. Daylight saving time does not have to be considered.