Fibonacci String#2525
Sign in

Fibonacci String

1 second
32 megabytes
Very easy

After little Jim learned about Fibonacci numbers in class, he became very interested in them. Now he is thinking about a new concept — Fibonacci strings.

He defines Fibonacci strings as follows:

s_n = s_{n-1} + s_{n-2}, n > 1

Jim is so fascinated by Fibonacci strings that whenever someone gives him two strings s_0 and s_1, he immediately starts computing s_2, s_3, s_4, s_5, and so on.

For example, if s_0 = "ab" and s_1 = "bc", then the following strings are obtained:

s_2 = "abbc", \\ s_3 = "bcabbc", \\ s_4 = "abbcbcabbc" \\ and~so~on

Since the strings grow very quickly, Jim cannot write them out completely. Therefore, he is only interested in how many times each letter appears in the -th Fibonacci string.

Input

The first line contains the number of test cases . Each test case consists of two initial strings s_0, s_1 and an integer k~(0 \le k < 50). Each input string consists of no more than lowercase Latin letters.

Output

For each test case, count how many times each letter appears in the -th Fibonacci string and print the result in the format x:n (see the sample output).

The outputs for different test cases should be separated by a blank line.

Examples

Example 1

Loading
Loading