Строки Фибоначчи
После того, как маленький Вася в классе узнал о числах Фибоначчи, он проявил к ним большой интерес. Но теперь он размышляет о новом понятии - строках Фибоначчи.
Он определяет: str_n = str_{n-1} + str_{n-2} при n > 1.
Он настолько обезумел от строк Фибоначчи, что если кто-то дает ему две строки str_0 и str_1, он начинает записывать str_2, str_3, str_4, str_5, ....
Например, если str_0 = "ab" и str_1 = "bc", то он получает str_2 = "abbc", str_3 = "bcabbc", str_4 = "abbcbcabbc", …
Так как строки очень быстро стают слишком длинными, Вася не может записать все строки в тетрадку. Поэтому он просто хочет знать, сколько раз каждая буква появляется в k-ой строке Фибоначчи. Можете ли вы помочь ему?
Входные данные
Первая строка содержит количество тестов n. Каждый тест в отдельной строке содержит две исходных строки str_0, str_1 и целое число k (0 ≤ k < 50). Исходные начальные строки содержат менее 30 латинских букв в нижнем регистре.
Выходные данные
Для каждого теста следует подсчитать сколько раз каждая буква появляется в k-ой строке Фибоначчи и вывести ответ в формате "x:n" (см. пример выходных данных). Разные тесты разделяйте пустой строкой.
Чтобы сделать эту задачу легче, можно предположить, что результат будет в диапазоне int.