#216552. [GKS 2015 #D] Virtual Rabbit

Alice just bought a virtual pet rabbit. The rabbit hops around on a screen and can be "fed" by pressing a button. Alice is fond of the rabbit, but she is also busy, and doesn't want to spend too much time taking care of it. However, if the rabbit goes without "food" for too long, it "dies" and Alice loses the game.

Every day, Alice gets up at time , goes to work at time , returns home at time , and goes to bed at time . Alice cannot feed the rabbit while she is at work or asleep -- that is, in the intervals and . Note that times and themselves are not valid feeding times, whereas times and are. In any other second, Alice can either push a button to instantly feed the rabbit, or not push the button. Between every two seconds, the rabbit determines the number of consecutive seconds in which it has not been fed, and "dies" if that duration is equal to .

It is currently 00:00:00 on Day 0, and the rabbit has just been delivered to Alice's house by the mail service. (The mail carrier pushes the button at 00:00:00, even if Alice is asleep, and then leaves.) Alice wants to make sure the rabbit is still "alive" at 00:00:00 on day . What is the minimal number of times that she needs to feed the rabbit, if she can keep the rabbit "alive" at all?

The first line of the input gives the number of test cases, . test cases follow; each consists of lines. The first lines represent the times , , , , and in "hh:mm:ss" format. The last line consists of one integer .

For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and is the minimal number of times Alice needs to feed the rabbit. If it's impossible for the rabbit to be alive at 00:00:00 on day , output -1.

样例输入 1

3
08:00:00
09:00:00
18:00:00
22:00:00
12:00:00
100
08:00:00
09:00:00
18:00:00
22:00:00
01:00:00
1
00:00:00
12:00:00
12:00:01
23:59:59
00:00:02
2

样例输出 1

Case #1: 200
Case #2: -1
Case #3: 86401

In sample case #1, Alice could feed the rabbit at 08:00:00 and 20:00:00 every day.

In sample case #2, the poor rabbit will be "dead" before Alice even wakes up on Day 0.

Limits

.

It's guaranteed that Alice always goes to bed before midnight and gets up at or after midnight.

, and are in strictly increasing order within the same day.

.

.

Small dataset (Test Set 1 - Visible)

.

Large dataset (Test Set 2 - Hidden)

.