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