Typing monkey

You have a monkey that can work a typewriter. It types lowercase English letters one at a time, without stopping, drawing each letter from a fixed probability distribution, and the keypresses are independent of one another.

You believe the monkey will eventually type out the complete works of Shakespeare. Your friend believes it is more likely to write another novel in the Harry Potter series. To settle the argument, shrink each work down to a single word and compute the probability that one word turns up before the other.

A word is produced the moment it appears as a substring of the letters the monkey has typed so far. Given two words $P$ and $Q$, compute the probability that the monkey produces $P$ before $Q$.

The first line contains the number of test cases $T$.

Each test case takes two lines. The first line contains the probabilities $p_a, p_b, \ldots, p_z$ of the monkey typing each letter from a to z, in that order, separated by single spaces. The second line contains the two strings $P$ and $Q$, separated by one space. Both strings consist of lowercase English letters only.

• $0 < T \le 100$
• $0 \le p_\alpha \le 1$ and $\sum_\alpha p_\alpha = 1$
• $0 < |P|, |Q| \le 16$
• $P$ and $Q$ are different.
• Every letter that occurs in $P$ or in $Q$ has probability greater than zero.
• No input makes the monkey complete $P$ and $Q$ at the same moment.

For each test case, print on its own line the probability that the monkey produces $P$ before $Q$. Round the value at the seventh digit after the decimal point and always print exactly six digits after the decimal point.