Decision Tree

A decision tree, and in particular the kind called a classification tree, is a data structure that sorts items into categories by reading the features of those items. Say that every animal is either cute or not cute. Given one animal, you decide whether it is cute by reading its features off the decision 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. It always has a root node and a weight. It may also have a feature name and two subtrees, and those subtrees are decision trees themselves.

Written out formally, a decision tree follows this grammar.

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

The part inside the square brackets [] is optional. The parentheses ( and ), the weight and the feature are all tokens. Between any two tokens there is at least one whitespace character, except that whitespace may be absent right after an opening parenthesis and right before a closing parenthesis. The whitespace characters are the space and the newline.

To work out how likely the animal is to be cute, set $p$ to 1 and start at the root of the tree. At each node, multiply $p$ by the weight of that node. If the node is a leaf, meaning it has no subtrees, stop there, and 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, descend into the first subtree and repeat the same process; if it does not, descend into the second subtree and repeat.

For example, a beaver has two features, furry and freshwater. Set $p$ to 1, start at the root and multiply by the root weight 0.2. The beaver is furry, so descend into the first subtree and multiply by 0.81, which makes $p$ equal to 0.162. The beaver is not fast, so from there descend into the second subtree. Finally multiply by 0.2 to get 0.0324. That is the probability that the beaver is cute.

You are given one decision tree and a list of animals with their features. For each animal, find the probability that it is cute.

The first line holds the number of test cases $N$. Then $N$ test cases follow.

The first line of each test case holds $L$, the number of lines used to write the decision tree. The next $L$ lines hold a decision tree in the format above. The line after that holds $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 only 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 feature name is a string of 1 to 10 lowercase English letters.
• Animal names within one test case are distinct.
• Feature names for one animal are distinct.
• Each of the $L$ lines that write out a decision tree holds at most 80 characters, not counting the newline.
• $1 \le L \le 100$
• $1 \le A \le 10$
• $0 \le n \le 5$

For each test case, first print one line of the form Case #x:, where $x$ is the test case number starting at 1. Then print exactly $A$ lines in the order the animals appear in the input, each holding the probability that the animal is cute, rounded to seven decimal places.

Always pad the fractional part to seven digits, so write 0.0324000 and 1.0000000. Round a trailing five up. No answer in the input lies exactly halfway between two values with seven decimal places.