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). Якщо межа не існує, виведіть один знак мінус (-).