Given a set of pattern strings, and a text, you have to find, if any of the pattern is a substring of the text. If any of the pattern string can be found in text, then print ‘yes’, otherwise ‘no’ (without quotes). But, unfortunately, thats not what is asked here. The problem described above, requires a input file generator. The generator generates a text of length L, by choosing L characters randomly. Probability of choosing each character is given as priori, and independent of choosing others. Now, given a set of patterns, calculate the probability of a valid program generating “no”. Input First line contains an integer T, the number of test cases. Each case starts with an integer K, the number of pattern strings. Next K lines each contain a pattern string, followed by an integer N, number of valid characters. Next N lines each contain a character and the probability of selecting that character, pi. Next an integer L, the length of the string generated. The generated text can consist of only the valid characters, given above. There will be a blank line after each test case. Output For each test case, output the number of test case, and the probability of getting a “no”. Constraints: • T ≤ 50 • K ≤ 20 • Length of each pattern string is between 1 and 20 • Each pattern string consists of only alphanumeric characters (a to z, A to Z, 0 to 9) • Valid characters are all alphanumeric characters ∑ • pi=1 • L ≤ 100 Sample Input 2 1 a 2 a 0.5 b 0.5 2 2 ab
2/2 ab 2 a 0.2 b 0.8 2 Sample Output Case #1: 0.250000 Case #2: 0.840000