Cirno and Marisa are playing a coin tossing game. Each time Cirno given a sequence of head(H) and tail(T) with the length of n. Then Marisa needs to give another sequence of n continuous speculation. Then, they begin to toss the coin until the last n times of tossing matches one of their speculations. The one who gives the right guess wins the game.

By now, Cirno has lost the game a lot of times. He wants to know the probability of winning the game.

There are multiple test cases. Each test case has one line with two strings made up with characters 'H' and 'T' separated by a blank. The length of each string is n. (n<=27)

The first string stands for Cirno's prediction.

Print the winning rate of Cirno in irreducible fraction in one line.