FATAWY  Fatawy
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 repost a Fatwa and make some small modifications to this Fatwa before reposting 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
Explantation:the LCS between (ABC,ABB) = 2, Len(ABC) = 3, Len(ABB)=3, Len(ACC)=3
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)
LCS / Len(ABC) = 66.66 >= 60% && LCS / Len(ABB) = 66.66 >= 60%
so ABC and ABB considered to be on the same topic.
are considered to be on the same topic.
hide comments
Sigma Kappa:
20170921 21:01:51
Should be moved to tutorial. 

Vipul Srivastava:
20170613 20:38:59
Its not that both should be bigger than TH, instead both should be bigger or equal to TH. 

shikhar jindal:
20160430 12:25:07
let n = 3 , th = 50.


shikhar jindal:
20160430 10:20:42
what will be the number of test cases? 

Mohit Pandey:
20150620 19:41:03
12 WAs for using real number arithmetic, changed it to integer and typecasted double for fun and AC!! 

rishabhtwr07:
20150114 21:14:40
@Mostafa "If Fatwa 'X' is on the same topic of Fatwa 'Y', and Fatwa 'X' is on the same topic of Fatwa 'Z', then Fatwa 'Y' is on the same topic of fatwa 'Z'" how so ?? lets say X = "AB" ; Y = "AA" ; Z = "BB" if TH =50 ; (X > Y) and (X > Z) but Y is not on the same topic of Z .. . pls explain !


Sudarshan K:
20141219 11:53:55
When used C++ string  AC :) WA with char arrays. 

Rishav Goyal:
20140210 17:18:13
don't apply if( f(arg)), gives WA on spoj!. 

Aradhya:
20130331 06:30:31
for kids ! Enjoy babies :)


:D:
20130131 11:10:47
Can you make it more clear in the description that the percentage actually means length percentage. Simply write "Values of fractions len(lcs)/len(A) and len(lcs)/len(B) in percent must both be bigger than TH." Right now it's very hard to read and Only the explanation clears it.

Added by:  Mostafa Saad Ibrahim 
Date:  20121110 
Time limit:  4s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  11th Egyptian Collegiate Programming Contest 