Circle Routes

문제 정보

문제

The city of Algospot has lots of circle bus routes. A circle bus route means the bus’s route ends at where it started. Donghyun runs a bus company, which will be servicing a new circle bus route. He wants to find out the minimum number of buses he needs to meet the bus schedule. The schedule works like this:

  1. Every day, the first bus departs from the terminal at time S.
  2. After that, a new bus will depart from the terminal periodically, with a fixed interval D. For example, a new bus will depart at time S, S+D, S+2D, and so on.
  3. The last bus of the day departs the terminal at E. (You can assume the difference between E and S is a multiple of D.)
  4. Each bus takes a fixed amount of time, C, to traverse the route and come back to the terminal.

For example, let’s assume the following scenario: the first bus departs at 05:50, and a new bus departs every 30 minutes until the last bus departs at 20:20. How many buses do we need, if it takes 65 minutes for a bus to traverse the route?

The first bus departs at 05:50 and returns to the terminal at 06:55. The second bus departs at 06:20 and returns at 07:25. The third bus departs at 06:50, and returns at 07:55. The fourth bus must depart at 07:20 - but at this time, the first bus is already back in the terminal, so Donghyun only needs 3 buses to serve this schedule.

Write a program to find the minimum number of buses.

입력

The first line of the input gives the number of test cases T. (1 \le T \le 10\,000) T lines follow, each containing a test case. The test case consists of four strings S, E, D and C, in the form HH:MM. S, E (S \le E) represent the time of the first and the last bus, respectively. D and C (0 < D, 0 < C) each represent the time interval between buses, and the time it takes a bus to traverse the route.

In each string HH:MM, HH represents the hour part of the time (or time interval), and MM represents the minute part. Concretely, HH will be a zero-padded integer between 0 and 23 (00, 01, \cdots, 23). Likewise, MM will be a zero-padded integer between 0 and 59 (00, 01, \cdots, 59).

출력

Print a single line per each test case, containing the minimum number of buses required for the schedule.

예제 입력

4
05:50 20:20 00:30 01:05
05:50 20:20 00:30 01:00
05:00 20:00 15:00 16:00
01:00 23:00 00:10 21:39

예제 출력

3
2
2
130

노트

0개의 댓글이 있습니다.