{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eWe define a string of length \\(l\\) as an array \\(S[1..l]\\). All the elements within it belongs to a finite set \\(\\sum\u003d\\{a,b,...,z\\}\\).\u003c/p\u003e\r\n\r\n\u003cp\u003eLet \\(\\text{Prefix}(S,i)\u003dS[1..i]\\) be one prefix of \\(S\\) with a length of \\(i\\).\u003c/p\u003e\r\n\r\n\u003cp\u003eSimilarly, \\(\\text{Suffix}(S,j)\u003dS[j..l]\\) denotes one \\(S\\)\u0027s suffix of length \\(l-j+1\\).\u003c/p\u003e\r\n\r\n\u003cp\u003eNow DreamGrid gives you a string multi-set \\(\\{S_{n}\\}\\) with the cardinality of \\(n\\), and \\(q\\) \u003cem\u003enot so hard\u003c/em\u003e tasks:\u003c/p\u003e\r\n\r\n\u003cp\u003eFor every task, you will receive two integers \\(i, j\\) (\\(i \\ne j\\)) denoting the \\(i\\)-th and the \\(j\\)-th string in the aforementioned multi-set. You have to calculate the \u003cstrong\u003elongest\u003c/strong\u003e string \\(S^{\u0027}\\) which satisfies the following two conditions at the same time.\u003c/p\u003e\r\n\u003col\u003e\r\n \u003cli\u003e\\(S^{\u0027}\\) is both the suffix of \\(S_{i}\\) and \\(S_{j}\\)\u003c/li\u003e\r\n \u003cli\u003eThere exists at least one string \\(S_{k}\\in\\{S_{n}\\}\\) that \\(S^{\u0027}\\) is the prefix of \\(S_{k}\\). Let the number of such strings be \\(|\\{S_{k}\\}|\\) (Obviously, \\(\\{S_{k}\\}\\), which is also a multi-set, is a subset of \\(\\{S_{n}\\}\\)).\u003c/li\u003e\r\n\u003c/ol\u003e\r\n\r\n\u003cp\u003eIf such \\(S^{\u0027}\\) doesn\u0027t exist, you have to print a character \u0027N\u0027(without quotes). Otherwise your program should print \\(|\\{S_{k}\\}|\\) in one line.\u003c/p\u003e\r\n\r\n\u003ch4\u003eInput\u003c/h4\u003e\r\n\r\n\u003cp\u003eThere are about 10 test cases.\u003c/p\u003e\r\n\r\n\u003cp\u003eFor every test case, the first line contains an integer \\(n\\) (\\( 1 \\le n \\le 10^5\\)).\u003c/p\u003e\r\n\r\n\u003cp\u003eThe next \\(n\\) lines each contains a lowercased string \\(S_{i}\\). We guarantee that \\(1 \\le \\sum_{i\u003d1}^{n}|S_{i}|\\le 5\\times 10^5\\) and each string is not empty.\u003c/p\u003e\r\n\r\n\u003cp\u003eThe next line contains an integer \\(q\\) (\\(1 \\le q \\le 10^5\\)).\u003c/p\u003e\r\n\r\n\u003cp\u003eAnd the final \\(q\\) lines each contains two integers \\(i, j\\) (\\(1 \\le i, j \\le n\\), \\(i \\ne j\\)).\u003c/p\u003e\r\n\r\n\u003ch4\u003eOutput\u003c/h4\u003e\r\n\r\n\u003cp\u003eFor every query, print the answer as the description narrates.\u003c/p\u003e\r\n\r\n\u003ch4\u003eSample\u003c/h4\u003e\n\u003ctable class\u003d\"vjudge_sample\"\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\nab\r\ncb\r\nde\r\n2\r\n1 2\r\n2 3\r\n7\r\nxabcd\r\nyabcd\r\ncdo\r\ncdp\r\ncdq\r\ncdr\r\nabcdz\r\n1\r\n1 2\r\n3\r\naa\r\naa\r\naa\r\n1\r\n1 3\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eN\r\nN\r\n1\r\n3\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\r\n"}}]}