A super shop sells only 26 items, labeled them from ‘A’ to ‘Z’. The shop stores the list of products bought by every customer as transactions.
A transaction is a set of products bought by a customer which is represented as a string. For example “ACGBD” is a transaction which means products A, C, G, B, D are bought by a particular customer. Note that all the characters of a transaction string are distinct.
At the end of the day the super shop has a big list of N transactions.
Now, let X and Y be two sets of products and [ X ∩ Y = 𝜙 ], that is X and Y have no common elements. For example X = “ABD” and Y = “CEF” is valid , whereas X = “ABC” and Y = “CDE” is not valid .
It is guaranteed that there exists at least one transaction which contains all the elements of set X.
Now you are given a list of N transactions. You have to find out the probability that a transaction string having the elements of X also contains the element of Y.
The first line contains the number of test cases t (1 ≤ t ≤ 20). Then t cases follow.
Each of the test case contains two integers N and M (1 ≤ N, M ≤ 1000) in the first line. Then N lines follow. Each of those line contains a string T (1 ≤ T ≤ 26), consists of only upper case letters, denote a transaction as described above.
Then there will be M queries. Each of the query contains two lines. First line is X (1 ≤ |X| ≤ 26) and the second line is Y (1 ≤ |Y| ≤ 26).
For each test cases first print “Case #:” in one line (where “#” is the case number, starting from 1). Then a new line follows.
Then print M lines each containing the probability P (up to 2 decimal places), that a transaction having the elements of X also contains the element of Y.
Input | Output |
---|---|
2 3 3 ABCDE ABD ACD A B AC D EA Z 2 1 XACDEGHTNOIK ZXTANIKGCH ACGH TONIK | Case 1: 0.67 1.00 0.00 Case 2: 0.50 |