Рядки Фібоначчі#2525
Після того як маленький Джим дізнався на уроці про числа Фібоначчі, вони його дуже зацікавили. Тепер він розмірковує про нове поняття — рядки Фібоначчі.
Він визначає рядки Фібоначчі наступним чином:
Джим настільки захоплений рядками Фібоначчі, що якщо хтось дає йому два рядки s_0 і s_1, він одразу починає обчислювати s_2, s_3, s_4, s_5 і так далі.
Наприклад, якщо s_0 = "" і s_1 = "", то отримуються наступні рядки:
Оскільки рядки ростуть дуже швидко, Джим не може виписати їх повністю. Тому його цікавить лише те, скільки разів кожна літера зустрічається в -му рядку Фібоначчі.
У першому рядку міститься кількість тестів . У кожному тесті задані два початкові рядки s_0, s_1 і ціле число k~(0 \le k < 50). Кожен вхідний рядок складається з менш ніж малих латинських букв.
Для кожного тесту необхідно порахувати, скільки разів кожна літера зустрічається в -му рядку Фібоначчі, і вивести результат у форматі x:n (див. приклад виводу).
Результати для різних тестів слід розділяти порожнім рядком.
Приклад 1