Probability Paradox

A fair coin is tossed over and over. Each toss shows H or T with probability $1/2$, so any two toss sequences of the same length are equally likely. A length 3 sequence such as HHH or THH has probability $1/8$.

Now consider this two-player game. Each player picks a pattern of coin flips, and the two patterns have the same length and differ from each other. The first player might pick HHH while the second picks THH. Both players then keep watching the same coin as it is flipped, and whoever sees their own pattern appear first wins. If the flips begin HHTHTTHH, the second player wins, because the last three flips spell THH.

Given the two patterns, how likely is the first player to win? Since the coin is fair, many people assume the patterns do not matter and that each player wins with probability $1/2$. That assumption is wrong, and the mistake is common enough to have a name, the Probability Paradox.

For some pairs the first player does win with probability exactly $1/2$. By symmetry, TT and HH are equally likely to appear first.

Go back to the first example, HHH against THH. Here the first player wins only when the first three tosses are all H. Suppose the earliest HHH did not start at the very beginning. Then some toss comes immediately before it and the whole sequence looks like ...?HHH. That ? cannot be an H, because ...HHHH already completes HHH one toss earlier, and the game would have ended there. It cannot be a T either, because ...THHH completes THH first, so the second player would have already won. For HHH against THH, then, the first player wins exactly when the first three flips are H, which happens with probability $1/8$.

One more example: if the first player picks TTH and the second picks THH, the first player wins with probability $2/3$. Write a program that computes such a probability.

The input contains one or more datasets, one per line. Each line holds two patterns written with the characters H and T only. The two patterns have the same length and differ from each other, and a single space separates them. The common length is between 1 and 9, inclusive. The last line contains only $.

For each dataset, print on its own line the exact probability that the first pattern appears before the second one in a random sequence of fair coin tosses. State the probability as a rational number reduced to lowest terms, with a / between the numerator and the denominator. Both players have a nonzero chance of winning, so this value is always strictly between 0 and 1.

Warning: every final numerator and denominator fits in a 32-bit integer. Depending on your approach, intermediate values may need 64-bit integers (long in Java, long long in C++), and even then overflow is easy to hit.