POLSKI SPOJ

Fibonacci

Dzisiaj na lekcji matematyki dzieci dowiedziały się o ciągu Fibonacciego. I tak powstała gra, którą od razu wymyślili Jasiu i Stasiu. Zasady są proste. Stasiu podaje dwa słowa, które są pierwszymi wyrazami ciągu oraz liczbę całkowitą k. Kolejne wyrazy ciągu powstają poprzez konkatenację dwóch poprzednich wyrazów. I tak na przykład dla dwóch pierwszych wyrazów: ot i co dalej otrzymujemy: otco, cootco, otcocootco, itd.. Jasiu musi wyznaczyć k-ty wyraz ciągu, którego dwa pierwsze wyrazy są zdefiniowane przez Stasia. Ponieważ ciąg bardzo szybko rośnie i niektórych wyrazów nie sposób zapisać w rozsądnym czasie, wystarczy, że Jasiu poda ile razy pojawia się każda litera alfabetu w k-tym wyrazie ciągu.

Wejście
W pierwszym wierszu wejścia znajduje się liczba całkowita d (0 < d < 100) oznaczająca liczbę zestawów danych. W kolejnych wierszach znajdują się zestawy danych. Każdy zestaw składa się z dwóch ciągów złożonych z małych liter alfabetu łacińskiego oraz liczby całkowitej k (1 ≤ k ≤ 50). Długość dwóch ciągów nie przekracza łącznie 30 znaków.

Wyjście
Dla każdego zestawu należy wypisać ciąg 26-ciu liczb całkowitych, które w kolejności występowania oznaczają liczbę poszczególnych liter (a-z) w k-tym wyrazie ciągu.

Przykład

Wejście
3
fraktal to 3
fajny konkurs 4
ot co 5

Wyjście
2 0 0 0 0 1 0 0 0 0 1 1 0 0 1 0 0 1 0 2 0 0 0 0 0 0
1 0 0 0 0 1 0 0 0 1 4 0 0 3 2 0 0 2 2 0 2 0 0 0 1 0
0 0 3 0 0 0 0 0 0 0 0 0 0 0 5 0 0 0 0 2 0 0 0 0 0 0