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.