Рядки Фібоначчі
Після того, як маленький Вася у класі взнав про числа Фібоначчі, він проявив до них велику цікавість. Але тепер він розмірковує над новим поняттям - рядках Фібоначчі.
Він визначає їх так: 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 (0 ≤ K < 50), відокремлені пропусками. Задані початкові рядки у вхідному файлі містять менше 30 латинських літер у нижньому регістрі.
Вихідні дані
Для кожного тестового випадку Ви повинні підрахувтаи, скільки разів кожна літера з'являється у K-му рядку Фібоначчі і вивести відповіь у форматі "X:N" (див. приклад вихідних даних). Різні тестові випадки відокремлюйте порожнім рядком.
Щоб зробити цю задачу простішою, можно припустити, що результат буде у діапазоні int.