AB-поэмы
AB-поэмы
Современная рекурсивная AB-поэма создается из заданного стиха W и двух фраз Pa
и Pb
, все они являются словами в алфавите {a, b}. Первый стих поэмы W1
= W, а n-ый стих получается из (n - 1)-го заменой каждой a в Wn-1
фразой Pa
, и каждой b фразой Pb
.
Вы организовываете ежегодное чтение AB-поэмы, по одному стиху каждый год. Оцените, как будет меняться время чтения стихов в будущем. Другими словами, найдите границу:
где |Wn
| обозначает общее количество букв в n-ом стихе поэмы.
Входные данные
Первая строка содержит количество тестов t. Каждый тест состоит из трех строк, каждая из которых содержит слово в алфавите {a, b}. Этими словами являются соответственно Pa
, Pb
и W. Слова не пустые и содержат не более 1000 символов.
Выходные данные
Для каждого теста в отдельной строке вывести одно действительное число: границу, вычисленную программой. Разрешена ошибка вычислений порядка 10-9
. Если граница не существует, вывести один знак минус (-).
2 ab a ab bb aaa baa
1.61803398875 -