{"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\"\u003eWe can generate a random string by generating a sequence of random characters and concatenating them together. Each character is chosen independently from the first n letters in the English alphabet with equal probability. Only capital letters are used in this problem. The generation is stopped as soon as one of specific patterns occurs in the random string.\u003cbr\u003e\u003cbr\u003eYour task is to predict the expected length of the generated string.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"Standard input will contain multiple test cases.\u003cbr\u003e\u003cbr\u003eFirst line is the number of case x.\u003cbr\u003e\u003cbr\u003eEach test case consists of integer N (1\u0026lt;\u003dN\u0026lt;\u003d8) which is the number of letters used, and M (1\u0026lt;\u003dM\u0026lt;\u003d10) which is the number of patterns used. The following M lines contain the patterns which are non-empty strings consisting of letters chosen from the first N upper case English letters. The length of any pattern will not exceed 10."}},{"title":"Output","value":{"format":"HTML","content":"For each test case, print the expected length of the generated random string. All output numbers are rounded to the second digit after the decimal point."}},{"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\u003e4\r\n2 1\r\nA\r\n2 1\r\nABA\r\n3 1\r\nAAAAA\r\n2 2\r\nA\r\nAA\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2.00\r\n10.00\r\n363.00\r\n2.00\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}