Fibonacci Sıraları
Kiçik Vasya sinifdə Fibonacci ədədləri haqqında öyrəndikdən sonra onlara böyük maraq göstərdi. İndi isə o, yeni bir anlayış - Fibonacci sətirləri üzərində düşünür.
O, bu sətirləri belə müəyyən edir: str[n] = str[n-1] + str[n-2] (n > 1)
Vasya Fibonacci sətirlərinə o qədər maraq göstərir ki, ona iki sətir str[0] və str[1] verildikdə, o, dərhal str[2], str[3], str[4], str[5], və s. yazmağa başlayır.
Məsələn:
Əgər str[0] = "ab"; str[1] = "bc";
o zaman nəticə olaraq str[2]="abbc", str[3]="bcabbc", str[4]="abbcbcabbc", və s. alır;
Sətirlər çox tez böyüdüyü üçün Vasya bütün sətirləri dəftərə yaza bilmir. Buna görə də o, yalnız K-cı Fibonacci sətirində hər bir hərfin neçə dəfə göründüyünü bilmək istəyir. Ona kömək edə bilərsinizmi?
Giriş verilənləri
Birinci sətir testlərin sayını göstərən tam ədəd N ehtiva edir. Sonra N test nümunəsi gəlir. Hər bir test nümunəsi ayrı bir sətirdə iki başlanğıc sətir str[0], str[1] və tam ədəd K (0 ≤ K < 50) ehtiva edir, boşluqlarla ayrılmışdır. Giriş faylında verilən başlanğıc sətirlər kiçik hərflərlə yazılmış 30 latın hərfindən az ehtiva edir.
Çıxış verilənləri
Hər bir test nümunəsi üçün K-cı Fibonacci sətirində hər bir hərfin neçə dəfə göründüyünü hesablamalı və nəticəni "X:N" formatında çıxarmalısınız (çıxış nümunəsinə baxın). Müxtəlif test nümunələrini boş sətirlə ayırın.
Bu tapşırığı asanlaşdırmaq üçün nəticənin int diapazonunda olacağını fərz etmək olar.