Fatawy is one of the most popular social networking site in Egypt during the last period. Every user is posting Fatwa through his profile to share his thoughts with his followers. And everyone can re-post a Fatwa and make some small modifications to this Fatwa before re-posting it.

Zezo was interested to analyze all Fatawy from his followers and know what are the trending topics they are discussing in Egypt on a given day. So he tried to model a system to extract some features from every Fatwa, such that every Fatwa can be represented by at most 10 features and every feature is represented by one Capital Alphabetic character. And through his system he decided to define a relation between Fatawy, that's fatwa 'A' is on the same topic as Fatwa 'B', if values of fractions length(lcs)/length(A) and length(lcs)/length(B) in percent must both be bigger than TH where: lcs is the longest common subsequence of the feature vector of Fatwa 'A' and feature vector of Fatwa 'B' and TH is a threshold percentage of the Fatwa length. If Fatwa 'A' is on the same topic of Fatwa 'B', and Fatwa 'A' is on the same topic of Fatwa 'C', then Fatwa 'B' is on the same topic of fatwa 'C'. (See sample 1 for details).

So as you all know that Zezo is not that good at programming and implementing this system, he will just help you by giving you the feature vector of every Fatwa, and he kindly ask you to find the number of different topics in that day.

Note: The longest common subsequence (LCS) problem is to find the longest subsequence common to all sequences in a set of sequences (often just two). And it is good to notice that substrings are consecutive parts of a string, while subsequences need not be.

Input

The first line of input contains an integer T that represents the number of test cases. Every following test case will start with a line contains two integers N and TH (1 <= N <= 500) number of Fatway in a given day and TH is an integer number in the interval ]0, 100[ which is the threshold percent as explained in the problem description, followed by N lines every line contains a single string F_i of uppercase characters where 1 <= length(F_i) <= 10.

Output

For each test case, output on a single line “Case #T:” where T is the number of the test case, followed by a line contains the number of trending topics in that day.

Example

Input:
2
3 60
ABC
ABB
ACC
5 80
BCCBC
AAABB
CACBC
CABCB
ABCAB

Output:
Case #1:
1
Case #2:
2

Explanation

the LCS between (ABC, ABB) = 2, Len(ABC) = 3, Len(ABB)=3, Len(ACC)=3

LCS / Len(ABC) = 66.66 >= 60% && LCS / Len(ABB) = 66.66 >= 60%

so ABC and ABB considered to be on the same topic.

The same Applies for ABC and ACC: (ABC, ABB) are on the same topic, (ABC, ACC) are on the same topic, so (ABC, ACC, ABB) are considered to be on the same topic.