Строки Фибоначчи
Строки Фибоначчи
После того, как маленький Вася в классе узнал о числах Фибоначчи, он проявил к ним большой интерес. Но теперь он размышляет о новом понятии - строках Фибоначчи.
Он определяет: 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-ой строке Фибоначчи. Можете ли вы помочь ему?
Giriş verilənləri
Первая строка содержит количество тестов n. Каждый тест в отдельной строке содержит две исходных строки str_0, str_1 и целое число k (0 ≤ k < 50). Исходные начальные строки содержат менее 30 латинских букв в нижнем регистре.
Çıxış verilənləri
Для каждого теста следует подсчитать сколько раз каждая буква появляется в k-ой строке Фибоначчи и вывести ответ в формате "x:n" (см. пример выходных данных). Разные тесты разделяйте пустой строкой.
Чтобы сделать эту задачу легче, можно предположить, что результат будет в диапазоне int.
Nümunə
1 ab bc 3
a:1 b:3 c:2 d:0 e:0 f:0 g:0 h:0 i:0 j:0 k:0 l:0 m:0 n:0 o:0 p:0 q:0 r:0 s:0 t:0 u:0 v:0 w:0 x:0 y:0 z:0