Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Super Shop

Limits 1s, 512 MB

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.

Input

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).

Output

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.

Sample

InputOutput
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


Discussion
Statistics

70% Solution Ratio

nfs277 Earliest, 2w ago

tahsinbd Fastest, 0.1s

nfs277 Lightest, 131 kB

Bruteforcekid Shortest, 825B

Submit

Login to submit