{"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\"\u003eUsing data compression technique, the long string ``ruiruiruiruiruirui\" can be compressed into ``(ruirui)3\" or ``(rui)6\". To simplify the technique, multiple compressions are not allowed. For example, we \u003cb\u003edon\u0027t allow\u003c/b\u003e to compress the string ``princessruiruiprincessruirui\" into ``(princess(rui)2)2\".\u003cbr\u003e\u003cbr\u003eNow for given string $S$ and $k$ patterns using the mentioned technique, we want to distinguish each pattern which is a prefix of $S$. We emphasize that a pattern as a string can be cyclic shifted. For example, a pattern ``abcd\" can be shifted into ``bcda\", ``cdab\" or ``dabc\".\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line contains an integer $t~(1\\le t\\le 13)$ which is the number of test cases.\u003cbr\u003e\u003cbr\u003eFor each test case, the first line is the string $S$. The second line contains the integer $k(1\\le k\\le 10)$ and following $k$ lines list the patterns, labelled from $1$ to $k$.\u003cbr\u003eThe string $S$ and all patterns only contain lower-case letters, numbers and parentheses. Numbers of replication are positive integers no more than $2\\times 10^8$. The length of $S$ is no more than $11000$. The length of each pattern is no more than $11000$ as well. We guarantee that the actual length of each $T$ (the length of the original pattern without compression) would be smaller than the actual length of $S$ (the length of original $S$ without compression). The length of each substring given in parentheses is no more than $10$."}},{"title":"Output","value":{"format":"HTML","content":"For each test case, output the sum of labels\u0027 squares for patterns as the prefix of $S$."}},{"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\u003e3\r\nz(rz)3r(rui)2cumt\r\n5\r\n(zr)4\r\nzrzrrui\r\nzr(zr)2z(r)2u\r\n(rz)3\r\n(zr)2z(r)2zr\r\n(ab)2aab(aba)3(ba)2(zhang)940712\r\n4\r\n(babaa)2(baa)2\r\n(aabab)2\r\n(ab)3\r\n(aba)2(ab)3a(ab)2(a)2b\r\n(a)100b(a)100c(a)100d\r\n1\r\n(a)100d(a)100c(a)100b\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase #1: 51\r\nCase #2: 21\r\nCase #3: 0\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cbr\u003e In the first test case, the string S is ``zrzrzrzrruiruicumt\". The first pattern ``zrzrzrzr\" is a prefix of S. The third one ``zrzrzrzrru\" is a prefix of S as well. The fourth on can be shifted into ``zrzrzr\" and the fifth one can be shifted into ``zrzrzrzrr\". The sum of squares is 1^2 + 3^2 + 4^2 + 5^2 \u003d 51.\u003cbr\u003e"}}]}