eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Рядки Фібоначчі

Рядки Фібоначчі

Ліміт часу 1 секунда
Ліміт використання пам'яті 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-му рядку Фібоначчі. Чи можете ви допомогти йому?

Вхідні дані

Перший рядок містить ціле число N, яке вказує кількість тестів. Далі йде N тестових прикладів. Кожен тестовий приклад у окремому рядку містить два початкових рядки str[0], str[1] та ціле число K (0K < 50), відокремлені пропусками. Задані початкові рядки у вхідному файлі містять менше 30 латинських літер у нижньому регістрі.

Вихідні дані

Для кожного тестового випадку Ви повинні підрахувтаи, скільки разів кожна літера з'являється у K-му рядку Фібоначчі і вивести відповіь у форматі "X:N" (див. приклад вихідних даних). Різні тестові випадки відокремлюйте порожнім рядком.

Щоб зробити цю задачу простішою, можно припустити, що результат буде у діапазоні int.

Приклад

Вхідні дані #1
1
ab bc 3
Вихідні дані #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