After little Jim learned Fibonacci Number in the class, he was very interest in it. Now he is thinking about a new thing - Fibonacci String. He defines: \textbf{str\[n\] = str\[n-1\] + str\[n-2\]} (\textbf{n} > \textbf{1}) He is so crazying that if someone gives him two strings \textbf{str\[0\]} and \textbf{str\[1\]}, he will calculate the \textbf{str\[2\]}, \textbf{str\[3\]}, \textbf{str\[4\]}, \textbf{str\[5\]}, .... For example : If \textbf{str\[0\]} = "\textbf{ab}"; \textbf{str\[1\]} = "\textbf{bc}"; he will get the result, \textbf{str\[2\]}="\textbf{abbc}", \textbf{str\[3\]}="\textbf{bcabbc}" , \textbf{str\[4\]}="\textbf{abbcbcabbc}", …; As the string is too long, Jim can't write down all the strings in paper. So he just want to know how many times each letter appears in \textbf{K}th Fibonacci String. Can you help him? \InputFile The first line contains a integer \textbf{N} which indicates the number of test cases. Then \textbf{N} cases follow. In each case, there are two strings \textbf{str\[0\]}, \textbf{str\[1\]} and a integer \textbf{K} (\textbf{0} ≤ \textbf{K} < \textbf{50}) which are separated by a blank. The string in the input will only contains less than \textbf{30} low-case letters. \OutputFile For each case,you should count how many times each letter appears in the \textbf{K}th Fibonacci String and print out them in the format "\textbf{X:N}". If you still have some questions, look the sample output carefully. Please output a blank line after each test case. To make the problem easier, you can assume the result will in the range of int.