eolymp
bolt
Try our new interface for solving problems
Məsələlər

Строки Фибоначчи

Строки Фибоначчи

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 32 MiB

После того, как маленький Вася в классе узнал о числах Фибоначчи, он проявил к ним большой интерес. Но теперь он размышляет о новом понятии - строках Фибоначчи.

Он определяет: 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ə

Giriş verilənləri #1
1
ab bc 3
Çıxış verilənləri #1
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