AB-poems#5542
A modern recursive -poem is constructed from a given verse and two key phrases P_a and P_b, all of them being words over the alphabet . The first verse of the poem is W_1 = , and the -th verse is constructed from the n - 1-th by replacing every in W_{n-1} with P_a, and every with P_b.
You are organizing an annual reading of an AB-poem, one verse every year. Try to estimate how the amount of time needed for future readings will change - in other words, compute the limit:
where |W_n| denotes the total number of letters in the -th verse of the poem.
The first line of standard input contains a single integer - the number of test cases. The test cases follow. A test case contains three lines, each line containing a word over . The three words in these lines are P_a, P_b and , respectively. Words are nonempty and do not exceed characters.
For each test case, your program should output a single line containing a single real number: the limit computed by the program. The allowed absolute error is 10^{-9}. If the limit does not exist, write a single minus () instead.
Example 1