После того, как маленький Вася в классе узнал о числах Фибоначчи, он проявил к ним большой интерес. Но теперь он размышляет о новом понятии - строках Фибоначчи. Он определяет: \textbf{str_n} = \textbf{str_\{n-1\} + str_\{n-2\}} при \textbf{n} > \textbf{1}. Он настолько обезумел от строк Фибоначчи, что если кто-то дает ему две строки \textbf{str_0} и \textbf{str_1}, он начинает записывать \textbf{str_2}, \textbf{str_3}, \textbf{str_4}, \textbf{str_5}, .... Например, если \textbf{str_0} = "\textbf{ab}" и \textbf{str_1} = "\textbf{bc}", то он получает \textbf{str_2 }= "\textbf{abbc}", \textbf{str_3 }= "\textbf{bcabbc}", \textbf{str_4 }= "\textbf{abbcbcabbc}", … Так как строки очень быстро стают слишком длинными, Вася не может записать все строки в тетрадку. Поэтому он просто хочет знать, сколько раз каждая буква появляется в \textbf{k-}ой строке Фибоначчи. Можете ли вы помочь ему? \InputFile Первая строка содержит количество тестов\textbf{ n}. Каждый тест в отдельной строке содержит две исходных строки \textbf{str_0}, \textbf{str_1} и целое число \textbf{k }(\textbf{0 }≤ \textbf{k }< \textbf{50}). Исходные начальные строки содержат менее \textbf{30 }латинских букв в нижнем регистре. \OutputFile Для каждого теста следует подсчитать сколько раз каждая буква появляется в \textbf{k-}ой строке Фибоначчи и вывести ответ в формате "\textbf{x:n}" (см. пример выходных данных). Разные тесты разделяйте пустой строкой. Чтобы сделать эту задачу легче, можно предположить, что результат будет в диапазоне \textbf{int}.