DONALDO  DONALDO
Donaldo
Donaldo is a great footballer. Since he is famous, he has lots of girlfriends. But the problem is, he isn't certain about the actual number of his girlfriends. So, he checked his mobile inbox. His girlfriends send him a lot of texts. But he knows that, none of them will send more than 1 text between I seconds of time interval. Given the exact times of received texts, Donaldo has to guess the minimum possible number of girlfriends he has.
Input
The first line contains T(the number of test cases, 0<=T<=50). Then T test cases follows.
Each test case starts with a line with N(number of texts in Donaldo's inbox, 0<=N<=20000). The following N lines contain a time of the format H:M:S (H=hour , M=minute, S=second, 0<=H<=23, 0<=M<=59, 0<=S<=59). The ith time is the exact time when ith text was received (1<=i<=N). The last line contains I (1<=I<=86400).
Note that,
1. A specific time can occur more than once.
2. The texts are opened randomly, so the times don't have any particular(increasing/decreasing) order.
3. The duration between sending and receiving a text is negligible.
4. Intervals are inclusive. (e.g. If an interval of 5 seconds starts at 0:0:55, it will end at 0:0:59).
Output
For each testcase, output a line containing “Case X: Y”, where X is the case number and Y is the minimum possible number of Donaldo's girlfriends.
Sample Input 
Output for Sample Input 
2 
Case 1: 3

Explanation
In the first test, all the texts are inside 86400 seconds duration. That means, each text is sent by a distinct girlfriend. So, number of Donaldo's girlfriends has to be greater or equal to 3.
In the second case, there are 2 possible time intervals containing 2 texts. One is containing the 1st and the 3rd time, and the other is containing the 1st and the 2nd time. So, any answer smaller than 2 is not possible.
hide comments
makhan_28:
20210418 06:19:26
Nice problem :) 

anshumanc007:
20181222 11:37:21
Last edit: 20181222 11:49:12 

m2do:
20180118 06:08:21
why is the output of


piyush_682:
20170608 13:30:39
One of the accepted solutions is giving the output


geety:
20151221 06:04:59
Hala Madrid ! Last edit: 20151221 06:17:18 

Dushyant Singh:
20150616 19:37:24
I love time related problems! :) Last edit: 20150619 14:07:46 

Petar Bosnjak:
20150124 16:57:17
Don't forget n can be 0 too! 

Hussain Kara Fallah:
20140131 14:33:30
Read Carefully


Vijay Jain:
20130707 04:34:33
nice question :) 

sacred:
20120725 20:27:12
please elaborate 2nd test case...or provide more test cases..

Added by:  Bidhan 
Date:  20120723 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Own Problem (Used in University of Dhaka's internal contest). Alternate Writer : Shiplu Hawlader, Zobayer Hasan. 