{"trustable":false,"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":"When deciding on the name of their band, anon came up with n strings. The band members decided to use these strings as inspiration to name the band, following these specific steps:\n\u003cbr\u003e\n1. Select two strings, $x$ and $y$. \u003cbr\u003e\n2. Among all the common substrings between the $x$-th and $y$-th strings, choose the longest common substring that is also a prefix of one of the $n$ strings (including $x$ and $y$).\u003cbr\u003e\n3. This selected substring becomes the name of the band. \u003cbr\u003e\n\u003cbr\u003e\nSince this method seems a bit hasty, they decided to perform multiple operations and then choose the most suitable string as the band name. They have sought your assistance in completing this task. They plan to perform this operation $k$ times. After selecting $x$ and $y$ in each operation, you don\u0027t need to print the final string that satisfies the condition, just print the length of that string.\n"}},{"title":"Input","value":{"format":"HTML","content":"The first line of the input contains an integer T, denoting the number of test cases.\n\u003cbr\u003e\nFor each test cases, the first line contains integer n (n ≤ 1e5)\n\u003cbr\u003e\nNext, there are n lines, each containing a string consisting of lower case letters. The total length of the strings will not exceed 1e5.\n\u003cbr\u003e\nAnd an integer k (1 ≤ k ≤ 100) is following, representing the number of operation.\n\u003cbr\u003e\nNext, there are k lines, each line contain two integers x, y, denoting the selected x-th and y-th strings \n"}},{"title":"Output","value":{"format":"HTML","content":"You should output the answers for each operation, one integer per line."}},{"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\n4\nanontokyo\nunknown\nanone\nannouimo\n2\n1 3\n1 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\n0\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}