AB-поеми#5542
Сучасна рекурсивна AB-поема створюється з початкового вірша і двох фраз P_a та P_b, які складаються зі слів в алфавіті . Перший рядок поеми W_1 дорівнює , а -ий рядок формується з (n - 1)-го шляхом заміни кожної в W_{n-1} на фразу P_a, а кожної на фразу P_b.
Ви організовуєте щорічне читання AB-поеми, читаючи по одному рядку щороку. Вам потрібно оцінити, як змінюватиметься тривалість читання рядків у майбутньому. Іншими словами, знайдіть межу:
де |W_n| позначає загальну кількість літер у -му рядку поеми.
Перший рядок містить кількість тестів . Кожен тест складається з трьох рядків, кожен з яких містить слово в алфавіті . Цими словами є відповідно P_a, P_b та . Слова не порожні і містять не більше символів.
Для кожного тесту в окремому рядку виведіть одне дійсне число: межу, обчислену програмою. Дозволена похибка обчислень порядку 10^{-9}. Якщо межа не існує, виведіть один знак мінус (-).
Приклад 1