Decision Tree (Large)

A decision tree, and in particular the kind called a classification tree, sorts items into categories by reading features of those items. For example, an animal is either cute or it is not, and you can decide whether a given animal is cute by walking the tree below.

(0.2 furry
  (0.81 fast
    (0.3)
    (0.2)
  )
  (0.1 fishy
    (0.3 freshwater
      (0.01)
      (0.01)
    )
    (0.1)
  )
)

A decision tree is defined recursively. Every tree has a root node with a weight. A node optionally also has a feature name and two subtrees, which are themselves decision trees.

The formal grammar is:

tree ::= (weight [feature tree tree])
weight is a real number between 0 and 1, inclusive
feature is a string of 1 or more lower case English letters

The part inside the square brackets [] is optional. The parentheses, the weight and the feature are tokens. Any two tokens are separated by at least one whitespace character, except that the whitespace may be missing right after an open parenthesis ( and right before a close parenthesis ). The whitespace characters are the space ' ' and the newline '\n'.

To find how likely an animal is to be cute, start at the root of the tree with $p = 1$. At each node, multiply $p$ by the weight of that node. If the node is a leaf, meaning it has no subtrees, stop: the value of $p$ is the probability that the animal is cute. Otherwise look at the feature stored in the node. If the animal has that feature, move into the first subtree and continue in the same way. If it does not have that feature, move into the second subtree instead.

For example, a beaver has two features, furry and freshwater. Start at the root with $p = 1$. Multiply $p$ by 0.2, the weight of the root, and move into the first subtree because the beaver is furry. There, multiply $p$ by 0.81, which makes $p$ equal to 0.162. Move into the second subtree because the beaver is not fast. Finally multiply $p$ by 0.2 and end with 0.0324, the probability that the beaver is cute.

You are given a decision tree and a list of animals with their features. Report the probability that each animal is cute.

The first line contains one integer $N$, the number of test cases. $N$ test case descriptions follow.

Each test case starts with a line containing an integer $L$, the number of lines that describe a decision tree. The next $L$ lines contain a decision tree in the format above. The line after that contains $A$, the number of animals. Each of the next $A$ lines describes one animal in this format:

animal n feature1 feature2 ... featuren

Limits

• $1 \le N \le 100$
• Every weight is between 0 and 1, inclusive.
• Every weight consists of digits and at most one decimal point.
• A weight neither starts nor ends with a decimal point.
• A weight has at most one 0 before the decimal point.
• Every animal name and every feature name is 1 to 10 lower case English letters.
• Animal names inside one test case are distinct.
• Feature names of a single animal are distinct.
• Each of the $L$ lines of one tree definition has at most 80 characters, not counting the newline.
• $1 \le L \le 100$
• $1 \le A \le 100$
• $0 \le n \le 100$

For each test case, print a line holding Case #x:, where $x$ is the test case number starting from 1. Then print exactly $A$ lines, one per animal, in the same order as the input.

Each of those lines holds the probability that the animal is cute, written with exactly 7 digits after the decimal point. Round to the nearest value at that precision, and round a value that falls exactly halfway up. The integer part is always 0 or 1, so a probability of 1 is printed as 1.0000000.