Современная рекурсивная 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. Если граница не существует, вывести один знак минус (-).