가상 토끼

Alice는 방금 가상 애완 토끼를 샀다. 토끼는 화면에서 이리저리 뛰어다니며, 버튼을 누르면 "먹이"를 줄 수 있다. Alice는 토끼를 좋아하지만 바쁘기도 해서, 토끼를 돌보는 데 너무 많은 시간을 쓰고 싶지는 않다. 하지만 토끼가 너무 오랫동안 "먹이"를 먹지 못하면 "죽고", Alice는 게임에서 진다.

매일 Alice는 시각 G에 일어나고, 시각 W에 출근하며, 시각 H에 귀가하고, 시각 B에 잠자리에 든다. Alice는 직장에 있거나 자는 동안에는 토끼에게 먹이를 줄 수 없다. 즉, 구간 [W, H)와 [B, G)에서는 먹이를 줄 수 없다. 시각 W와 B 자체는 먹이를 줄 수 있는 시각이 아니지만, 시각 H와 G는 먹이를 줄 수 있다는 점에 유의하라. 그 밖의 어떤 초에도 Alice는 버튼을 눌러 토끼에게 즉시 먹이를 주거나, 버튼을 누르지 않을 수 있다. 매 두 초 사이마다 토끼는 연속해서 먹이를 먹지 못한 초의 수를 확인하고, 그 시간이 X와 같으면 "죽는다".

현재는 0일의 00:00:00이며, 우편 배달을 통해 토끼가 방금 Alice의 집에 도착했다. (Alice가 자고 있더라도 우편배달부는 00:00:00에 버튼을 누른 뒤 떠난다.) Alice는 D일의 00:00:00에도 토끼가 여전히 "살아" 있도록 하고 싶다. 토끼를 계속 "살아" 있게 하는 것이 가능하다면, Alice가 토끼에게 먹이를 주어야 하는 최소 횟수는 얼마인가?

제한

시간 제한: 테스트 세트당 30초. 메모리 제한: 1 GB. 1 ≤ T ≤ 100. Alice는 항상 자정 전에 잠자리에 들고 자정 이후 또는 자정에 일어난다는 것이 보장된다. 같은 날 안에서 G, W, H, B는 엄격한 증가 순서로 주어진다. 00:00:00 ≤ G < W < H < B ≤ 23:59:59. 00:00:00 < X ≤ 23:59:59.

작은 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ D ≤ 1000.

큰 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ D ≤ $10^{14}$.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어지며, 각 테스트 케이스는 6개의 줄로 이루어진다. 처음 5개의 줄은 시각 G, W, H, B와 X를 "hh:mm:ss" 형식으로 나타낸다. 마지막 줄에는 하나의 정수 D가 주어진다.

각 테스트 케이스마다 "Case #x: y"을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며 1부터 시작하고, y는 Alice가 토끼에게 먹이를 주어야 하는 최소 횟수이다. D일의 00:00:00에 토끼가 살아 있는 것이 불가능하다면 -1을 출력한다.

예제 케이스 #1에서 Alice는 매일 08:00:00과 20:00:00에 토끼에게 먹이를 줄 수 있다.

예제 케이스 #2에서 불쌍한 토끼는 Alice가 0일에 일어나기도 전에 "죽어" 있을 것이다.