DONALDO - DONALDO

no tags 

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 i-th time is the exact time when i-th 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.

Example

Input:
2
3
8:39:17
17:17:17
21:59:59
86400
3
17:17:17
21:59:59
8:39:16
48042

Output:
Case 1: 3
Case 2: 2

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
NeW AcP: 2012-07-23 13:55:46

please check my problem id 7361790. please give a test case where it is wrong.please help. what is wrong?give a hint atleast.

Problemsetter : Your code fails on many of the cases. Now I'm confused about which hint to give. :s
Reply ->give atleast one test case ,as I cannot find one.
Problemsetter : Inbox can be empty!
Reply-> thanks,ok just tell me if the concept I m using correct or i need to rethink on it on my latest submission.

Last edit: 2012-07-23 19:40:20

Added by:Bidhan
Date:2012-07-23
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.