AB-poems
A modern recursive AB-poem is constructed from a given verse W and two key phrases P[a] and P[b], all of them being words over the alphabet {a, b}. The first verse of the poem is W[1] = W, and the n-th verse is constructed from the n - 1-th by replacing every a in W[n-1] with P[a], and every b 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 n-th verse of the poem.
Input
The first line of standard input contains a single integer t - the number of test cases. The test cases follow.A test case contains three lines, each line containing a word over {a, b}. The three words in these lines are P[a], P[b] and W, respectively. Words are nonempty and do not exceed 1000 characters.
Output
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.