{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eAfter little Jim learned Fibonacci Number in the class , he was very interest in it.\u003cbr\u003eNow he is thinking about a new thing -- Fibonacci String .\u003cbr\u003e\u003cbr\u003eHe defines : str[n] \u003d str[n-1] + str[n-2] ( n \u0026gt; 1 ) \u003cbr\u003e\u003cbr\u003eHe is so crazying that if someone gives him two strings str[0] and str[1], he will calculate the str[2],str[3],str[4] , str[5].... \u003cbr\u003e\u003cbr\u003eFor example :\u003cbr\u003eIf str[0] \u003d \"ab\"; str[1] \u003d \"bc\";\u003cbr\u003ehe will get the result , str[2]\u003d\"abbc\", str[3]\u003d\"bcabbc\" , str[4]\u003d\"abbcbcabbc\" …………;\u003cbr\u003e\u003cbr\u003eAs the string is too long ,Jim can\u0027t write down all the strings in paper. So he just want to know how many times each letter appears in Kth Fibonacci String . Can you help him ?\u003cbr\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line contains a integer N which indicates the number of test cases.\u003cbr\u003eThen N cases follow.\u003cbr\u003eIn each case,there are two strings str[0], str[1] and a integer K (0 \u0026lt;\u003d K \u0026lt; 50) which are separated by a blank.\u003cbr\u003eThe string in the input will only contains less than 30 low-case letters.\u003cbr\u003e"}},{"title":"Output","value":{"format":"HTML","content":"For each case,you should count how many times each letter appears in the Kth Fibonacci String and print out them in the format \"X:N\". \u003cbr\u003eIf you still have some questions, look the sample output carefully.\u003cbr\u003ePlease output a blank line after each test case.\u003cbr\u003e\u003cbr\u003eTo make the problem easier, you can assume the result will in the range of int. \u003cbr\u003e"}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\nab bc 3\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003ea:1\r\nb:3\r\nc:2\r\nd:0\r\ne:0\r\nf:0\r\ng:0\r\nh:0\r\ni:0\r\nj:0\r\nk:0\r\nl:0\r\nm:0\r\nn:0\r\no:0\r\np:0\r\nq:0\r\nr:0\r\ns:0\r\nt:0\r\nu:0\r\nv:0\r\nw:0\r\nx:0\r\ny:0\r\nz:0\r\n\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}