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

Submit

Login to submit.

Contributors

Statistics

73% Solution Ratio
nfs277Earliest, Sep '19
nusuBotFastest, 0.0s
nfs277Lightest, 131 kB
SoudipShortest, 739B
Toph uses cookies. By continuing you agree to our Cookie Policy.